#include <iostream>
#include <fstream>

using namespace std;

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

int n, i, a[15], nr;
bool col[15], d1[28], d2[28];

int BKT(int k, int n)
{
    if(k<=n)
    {
        int i;
        for(i=1; i<=n; ++i)
        {
            if(col[i]==0 && d1[k+i-1]==0 && d2[n-k+i]==0)
            {
                a[k]=i;
                col[i]=1;
                d1[k+i-1]=1;
                d2[n-k+i]=1;
                BKT(k+1, n);
                col[i]=0;
                d1[k+i-1]=0;
                d2[n-k+i]=0;
            }
        }
    }
    else
    {
        ++nr;
        if(nr==1)
        {
            for(i=1; i<=n; ++i)
            {
                out<<a[i]<<" ";
            }
            out<<'\n';
        }
    }
}

int main()
{
    for(i=1; i<=15; ++i)
    {
        col[i]=0;
    }
    for(i=1; i<=28; ++i)
    {
        d1[i]=0;
        d2[i]=0;
    }
    in>>n;
    BKT(1, n);
    out<<nr;
    return 0;
}