#include <iostream>
using namespace std;
const int N = 20;
int path[N];
bool col[N], dg[N * 2], udg[N * 2];
int n, cnt;
void dfs(int t){
    if(t > n){
        cnt ++ ;
        if(cnt <= 3){
            for(int i = 1; i <= n; i ++ )    cout << path[i] << ' ';
            cout << endl;
        }
        return ;
    }
    for(int i = 1; i <= n; i ++ ){
        if(!col[i] && !dg[i + t] && !udg[i - t + n]){
            path[t] = i;
            col[i] = dg[i + t] = udg[i - t + n] = true;
            dfs(t + 1);
            col[i] = dg[i + t] = udg[i - t + n] = false;
        }    
    }
}
int main(){
    cin >> n;
    dfs(1);
    cout << cnt << endl;
    return 0;
}