#include <bits/stdc++.h>

using namespace std;

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

int n;
int sol;
int c[20];
bool col[20],diagp[20],diags[20];

void backt(int k){
    if(k==n+1){
        if(!sol){
            for(int i=1;i<=n;i++)
                out<<c[i]<<" ";
            out<<"\n";
        }        sol++;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!col[i] && !diagp[i-k+n] && !diags[i+k-1])
        {
            col[i]=1;
            c[k]=i;
            diagp[i-k+n]=1;
            diags[i+k-1]=1;
            backt(k+1);
            col[i]=0;
            diagp[i-k+n]=0;
            diags[i+k-1]=0;
        }
    }
}

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