#include <fstream>
using namespace std;

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

const int N=15;
int n, st[N], col[N], diag[3*N], diag2[3*N], sol;

void afis()
{
    for(int i=1;i<=n;++i)
        fout<<st[i]<<" ";
}
void bk(int k)
{
    if(k==n+1)
    {
        if(sol==0)afis();
        sol++;
        return;
    }
    for(st[k]=1;st[k]<=n;++st[k])
    {
        if(!col[st[k]]&&!diag[st[k]-k+n]&&!diag2[st[k]+k])
        {
            col[st[k]]=diag[st[k]-k+n]=diag2[st[k]+k]=1;
            bk(k+1);
            col[st[k]]=diag[st[k]-k+n]=diag2[st[k]+k]=0;
        }
    }
}
int main()
{
    fin>>n;
    bk(1);
    fout<<'\n'<<sol;
    return 0;
}