#include <iostream>
#include <fstream>
using namespace std;

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

int a[16][16],col[16],digp[32],digs[32],lin[16];
int n,nr;

void afis()
{
    if(nr==1)
        for(int i=1; i<=n; i++)
            g<<lin[i]<<' ';
}

void backt(int i)
{
    if(i>n)
    {
        nr++;
        afis();
        return;
    }

    for(int j=1; j<=n; j++)
    {
        if(0==digp[j-i+n] && 0==digs[i+j] && 0==col[j])
        {
            digp[j-i+n]=1;
            digs[i+j]=1;
            col[j]=1;
            lin[i]=j;
            backt(i+1);
            digp[j-i+n]=0;
            digs[i+j]=0;
            col[j]=0;
        }
    }

}

int main()
{
    f>>n;
    backt(1);
    g<<'\n';
    g<<nr;
    return 0;
}