#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

short n,v[13],l[13],d1[27],d2[27];
int s;

void bk(short i)
{
    if(i==n)
    {
        if(s==0)
            for(i=0;i<n;++i)
                fout<<v[i]+1<<" ";
        s++;
    }
    else
    {
        for(short j=0;j<n;++j)
        {
            if(l[j]==0 && d1[j-i+n-1]==0 && d2[j+i]==0)
            {
                v[i]=j;
                l[j]=1;
                d1[j-i+n-1]=1;
                d2[j+i]=1;
                bk(i+1);
                l[j]=0;
                d1[j-i+n-1]=0;
                d2[j+i]=0;
            }
        }
    }
}

int main()
{
    fin>>n;
    bk(0);
    fout<<"\n"<<s;
}