#include <bits/stdc++.h>
using namespace std;
int n,ud[1000];//  \左上右下,x-y恒等 j
int du[1000];//   /左下右上,x+y恒等 k
int l[1000];// 行，左右 y
int r[1000];//列，上下 x
int ans[1000];
int cnt=0;
int t=0;
void dfs(int val){
    if(val==n+1){
        if(t<3){
            for(int i=0;i<n;i++){
                cout<<ans[i]<<' ';
            }
            cout<<endl;
        }
        t++;
    }
    for(int i=1;i<=n;i++){
        int y=val,x=i;
        int j=abs(x-y),k=abs(x+y);
        if(l[y]==0&&r[x]==0&&ud[j]==0&&du[k]==0){
            l[y]++;
            r[x]++;
            ud[j]++;
            du[k]++;
            ans[cnt++]=i;
            dfs(val+1);
            ans[--cnt]=0;
            l[y]--;
            r[x]--;
            ud[j]--;
            du[k]--;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    dfs(1);
    cout<<t;
    return 0;
}