#include <iostream>
#include <fstream>

using namespace std;

int c[20], d1[40], d2[40], n, sol[20], l=0;
ofstream fout("damesah.out");

void afisare()
{
    for (int i=1; i<=n; i++)
        fout << sol[i] << " ";
    fout << "\n";
}

void bt(int k)
{
    if (k==n+1)
    {
        if (l<1)
            afisare();
        l++;
        return;
    }
    for (int i=1; i<=n; i++)
        if (!c[i] && !d1[i+k-1] && !d2[n-i+k])
        {
            c[i]=d1[i+k-1]=d2[n-i+k]=1;
            sol[k]=i;
            bt(k+1);
            c[i]=d1[i+k-1]=d2[n-i+k]=0;
        }
}

int main()
{
    ifstream fin("damesah.in");
    fin >> n;
    bt(1);
    fout << l;
    return 0;
}