#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n, v[20], sol;
bitset<30> a, b, c;

void bk(int r){
    if(r>n){
        if(!sol){
            for(int i=1; i<=n; i++)out<<v[i]<<" ";
            out<<"\n";
        }
        sol++;
        return;
    }
    for(int i=1; i<=n; i++){
        if(!c[i]&&!a[i-r+n-1]&&!b[r+i]){
            c[i]=1;
            a[i-r+n-1]=1;
            b[r+i]=1;
            v[r]=i;
            bk(r+1);
            c[i]=0;
            a[i-r+n-1]=0;
            b[r+i]=0;
        }
    }
}

int main(){
    in>>n;
    bk(1);
    out<<sol;
    return 0;
}