#include<bits/stdc++.h>
#include <cstring>
#include <iomanip>
using namespace std;

const int N = 105;

int path[N];
//col[i] 表示该行该列 dg[i]表示 主对角线 ， rdg[i]表示辅助对角线
bool col[N]={false} , dg[N]={false} ,rdg[N]= {false};

int n,cnt= 0; 

void dfs(int u){
    if(u == n){
        cnt++;
        if(cnt <=3){
            for(int i = 0 ;i< n;i++) cout << path[i] <<" ";
            cout << "\n";
        }
        return ;
    }
    //这里 i抽象为 列 ，u抽象为 行 分别对应  y = x+b y =-x+b （b= y-x +N (加上n之后同样也是唯一的) ） (b= y+x)
    for(int i = 1 ; i<=n;i++){   //从u行的第一列开始
        if(!col[i] && !dg[i+u] && !dg[n-i+u]){ // 剪枝
            path[u] = i;
            col[i] = dg[u+i] = rdg[n-i+u]  = true;
            dfs(u+1);
            col[i] = dg[u+i] = rdg[n-i+u]= false; // 回溯
        }
    }
}
int main()
{
    cin >> n;
    dfs(0);
    cout << cnt;
    return 0;

}