#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("damesah.in");
ofstream out ("damesah.out");
int dame[1005],f[1005],ok,nr,n,d1[1005],d2[1005];
void plas_dame(int poz){
    int i;
    if(poz>n){
        if(!ok){
            ok=1;
            for(int i=1;i<=n;i++)
                out<<dame[i]<<" ";
            out<<"\n";
        }
        nr++;
    }
    else{
        for(i=1;i<=n;i++){
            if(f[i]==0 && d1[i-poz+n]==0 && d2[i+poz]==0){
                f[i]=1;
                d1[i-poz+n]=1;
                d2[i+poz]=1;
                dame[poz]=i;
                plas_dame(poz+1);
                f[i]=0;
                d1[i-poz+n]=0;
                d2[i+poz]=0;
            }
        }
    }
}
int main()
{
    in>>n;
    plas_dame(1);
    out<<nr;
    return 0;
}