#include <iostream>
#include <fstream>
#define nmax 40

using namespace std;
bool ds[nmax],dp[nmax],viz[nmax];
int nr=0,n,st[nmax];
ifstream fin("damesah.in");
ofstream fout("damesah.out");

void gen(int k)
{
    if(k==n+1)
        {if(!nr){for(int i=1;i<=n;i++)
                fout<<st[i]<<' ';
                fout<<'\n';}
        ++nr;}
    else
    for(int i=1;i<=n;++i)
        if(!dp[i-k+n-1] && !ds[i+k] && !viz[i])
         {st[k]=i;
          dp[i-k+n-1]=ds[i+k]=viz[i]=true;
          gen(k+1);
          dp[i-k+n-1]=ds[i+k]=viz[i]=false;
         }


}

int main()
{
    fin>>n;
    gen(1);
   fout<<nr;

}