#include <iostream>
#include <cstdio>
#include <fstream>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
constexpr int NX = 30;
int n, sol[NX], viz[NX];
int vprin[NX], vsec[NX];
int found;
void afis()
{
    for(int i=1; i<=n; ++i)
        fout<<sol[i]<<" ";
    fout<<"\n";
}

void bec(int k)
{
    if(k>n)
    {
        if(found==0)
            afis();

        ++found;
        return;
    }
    for(int i=1; i<=n; ++i)
    {
        if(viz[i] + vprin[n+k-i] + vsec[k+i-1] == 0)
        {
            sol[k]=i;
            viz[i]=1;
            vprin[n+k-i]=1;
            vsec[k+i-1]=1;
            bec(k+1);
            viz[i]=0;
            vprin[n+k-i]=0;
            vsec[k+i-1]=0;
        }
    }
}
int main()
{
    fin>>n;
    bec(1);
    fout<<found;
    return 0;
}