#include <fstream>

using namespace std;

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

short n,v[13];
int s;

void bk(short i)
{
    if(i==n)
    {
        s++;
        if(s==1)
            for(short i=0;i<n;++i)
                fout<<v[i]<<" ";
    }
    else
    {
        bool b;
        short j,k;
        for(j=1;j<=n;++j)
        {
            for(k=0,b=0;k<i;++k)
            {
                if(v[k]==j || v[k]-j==i-k || v[k]-j==k-i)
                {
                    b=1;
                    break;
                }
            }
            if(b==0)
            {
                v[i]=j;
                bk(i+1);
            }
        }
    }
}

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