#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
ifstream si("damesah.in");
ofstream so("damesah.out");
int n,sol,poz[25];
bool f;
bitset<25> col;
bitset<45> diag1,diag2;
void backt(int x)
{
    int i;
    if(x==n+1)
    {
        if(!f)
        {
            for(i=1;i<=n;++i)
                so<<poz[i]<<' ';
            so<<'\n';
            f=true;
        }
        ++sol;
        return;
    }
    for(i=1;i<=n;++i)
    {
        if(!col[i]&&!diag1[n-x+i]&&!diag2[x+i-1])
        {
            col[i]=1;
            diag1[n-x+i]=1;
            diag2[x+i-1]=1;
            poz[x]=i;
            backt(x+1);
            col[i]=0;
            diag1[n-x+i]=0;
            diag2[x+i-1]=0;
        }
    }

}
int main()
{
    si>>n;
    backt(1);
    so<<sol;
    so.close();
    return 0;
}