#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX=20;
ifstream si("damesah.in");
//FILE*si=fopen("dominant.in","r");
ofstream so("damesah.out");
int n,sol,poz[NMAX];
bool f,col[NMAX],diag1[2*NMAX],diag2[2*NMAX];
void backt(int x)
{
    int i;
    if(x==n+1)
    {
        if(!f)
        {
            for(i=1;i<=n;++i)
            {
                so<<poz[i]<<' ';
            }
            so<<'\n';
            f=1;
        }
        ++sol;
        return;
    }
    for(i=1;i<=n;++i)
    {
        //printf("poz = %d candidat %d\n", x, i);
        if(!col[i]&&!diag1[n-x+i]&&!diag2[x+i-1])
        {
            poz[x]=i;
            col[i]=1;
            diag1[n-x+i]=1;
            diag2[x+i-1]=1;
            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;
}