n=int(input())
pos=[0]*(n+1)
c=[0]*(n+1)
p=[0]*(2*n+1)
q=[0]*(2*n+1)

ans=0
def dfs(x):
    global ans
    if x>n:
        ans=ans+1
        if ans<=3:
            for i in range(1,n+1):
                print(pos[i],end=" ")
            print()
        return
    for i in range(1,n+1):
        if c[i]==0 and q[x+i]==0 and p[x-i+n]==0:
            pos[x]=i
            c[i]=q[x+i]=p[x-i+n]=1
            dfs(x+1)
            c[i] = q[x + i] = p[x - i + n] =0
dfs(1)
print(ans)