#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
#define MAX_N 15
bool col[MAX_N], dp[MAX_N*2], ds[MAX_N*2];
int dame[MAX_N],rez,n;
void b(int l)
{
    if(l==n+1)
    {
        if(rez < 1)
            for(int i=1;i<=n;i++)
                g<<dame[i]<<" ";
        rez++;
    }
    else
    {
        for(int c=1;c<=n;c++)
        {
            if((!col[c]) && (!dp[c-l+n]) && (!ds[l+c]))
            {
                dame[l]=c;
                col[c] = dp[c-l+n] = ds[l+c] = 1;
                b(l+1);
                col[c] = dp[c-l+n] = ds[l+c] = 0;
            }
        }
    }
}
int main()
{
    f>>n;
    b(1);
    g<<'\n'<<rez;
    return 0;
}