#include <fstream>

using namespace std;

const char InFile[]="damesah.in";
const char OutFile[]="damesah.out";
const int MaxN=20;
const int MaxD=MaxN*3;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,bsol[MaxN],used[MaxN],diag1[MaxD],diag2[MaxD],sol[MaxN],cnt;

int K;

void back()
{
    ++K;
    if(K>N)
    {
        ++cnt;
        if(sol[1]==0)
        {
            for(register int i=1;i<=N;++i)
            {
                sol[i]=bsol[i];
            }
        }
    }
    else
    {
        for(register int i=1;i<=N;++i)
        {
            int d1=K+i;
            int d2=K-i+MaxN;
            if(!used[i] && !diag1[d1] && !diag2[d2])
            {
                used[i]=1;
                diag1[d1]=1;
                diag2[d2]=1;
                bsol[K]=i;
                back();
                used[i]=0;
                diag1[d1]=0;
                diag2[d2]=0;
            }
        }
    }
    --K;
}

int main()
{
    fin>>N;
    fin.close();

    back();

    for(register int i=1;i<=N;++i)
    {
        fout<<sol[i]<<" ";
    }
    fout<<"\n"<<cnt;
    fout.close();
    return 0;
}