#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int x[20],col[50],d1[50],d2[50],n,nr;
void btr(int k) {
    if(k>n){
        nr++;
        if(nr==1){
            for(int i=1;i<=n;i++)
                fout<<x[i]<<" ";
        fout<<"\n";
        }
    }
    for (int i=1;i<=n;i++) {
        x[k] = i;
        if (col[i]==0 && d1[n+i-k]==0 && d2[i+k]==0) {
            col[i] = 1;
            d1[n+i-k] = 1;
            d2[i+k] = 1;
            btr(k+1);
            col[i] = 0;
            d1[n+i-k] = 0;
            d2[i+k] = 0;
        }
    }
}
int main() {
    fin>>n;
    btr(1);
    fout<<nr;
    return 0;
}