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

ifstream in("damesah.in");
ofstream out("damesah.out");

int n, v[30], k;
bool fv[30], d1[30], d2[30];

void afis(){
    for(int i = 1; i <= n; i++)
            out<<v[i]<<" ";
    out<<"\n";
}

void bkt(int now){
    for(int i = 1; i <= n; i++)
        if(!fv[i] && !d1[now + i - 1] && !d2[n - now + i]){
        v[now] = i;
        fv[i] = d2[n - now + i] = d1[now + i - 1] = 1;
        if(now == n){
            if(!k)
                afis();
            k++;
        }
        bkt(now + 1);
        fv[i] = d2[n - now + i] = d1[now + i - 1] = 0;
    }
}

int main(){
    in>>n;
    bkt(1);
    out<<k;
}