#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,nrsol;
int x[100],fr[100],d1[100],d2[100];
void solutie()
{
    for(int i=1; i<=n; i++)
        fout<<x[i]<< " ";

}
int verifpr(int i,int j)
{
    /*
    1 5 6
    2 x x x
    3 x x x
      x x x
    {1}
    */
    if(i==j)
        return 1;
    if(i-j>0)
        return i-j+1;
    return j-i+n+1;
}
int verifsec(int i,int j)
{
    /*
      3 2 1
    x x x 5
    x x x 6
    x x x
    {1}
    */
    if(i+j==n+1)
        return 1;
    j=n-j+1;
    if(j<i)
    {
        return i-j+1;
    }
    return j-i+n+1;
}
void backtr(int pas)
{
    if(pas==n+1)
    {
        nrsol++;
        if(nrsol==1)
            solutie();
        return;
    }
    for(int i=1; i<=n; i++)
    {

        if(fr[i]==1)
            continue;
        x[pas]=i;
        fr[i]=1;
        int    diag1=verifpr(pas,i);
        int    diag2=verifsec(pas,i);
        if(d1[diag1]>0)
        {
            fr[i]=0;
            continue;
        }
        else d1[diag1]=1;

        if(d2[diag2]>0)
        {
            fr[i]=0;
            d1[diag1]=0;
            continue;
        }
        else
            d2[diag2]=1;

        d1[diag1]=d2[diag2]=1;
        backtr(pas+1);
        d1[diag1]=d2[diag2]=0;
        fr[i]=0;
    }
}
int main()
{
    fin>>n;
    backtr(1);
    fout<<
    "\n";
    fout<<nrsol;
}