#include <bits/stdc++.h>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");
int v[15],n,nrSol,c[15],diag1[50],diag2[50];
bool OK=true;
void Bkt(int poz)
{
    if(poz==n+1)
    {
        if(OK)
        {
            for(int i=1; i<=n; i++)
                g<<v[i]<<' ';
            OK=false;
        }
        nrSol++;

    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            v[poz]=i;
            if(!c[i]&&!diag1[i-poz+n-1]&&!diag2[i+poz])
                c[i]=diag1[i-poz+n-1]=diag2[i+poz]=true,Bkt(poz+1),c[i]=diag1[i-poz+n-1]=diag2[i+poz]=false;
        }
    }
}
int main()
{
    f>>n;
    Bkt(1);
    g<<'\n';
    g<<nrSol;
    return 0;
}