#include <iostream>
#include <fstream>

using namespace std;
int n, x[14],nrsol;
ifstream f("damesah.in");
ofstream g("damesah.out");
bool  valid(int k)
{
    for(int i=1; i<k;i++)
    if(x[k]==x[i]|| k-i==abs(x[k]-x[i]))
    return 0;
    return 1;
}
void afis()
{
    for(int i=1; i<=n;i++)
    g<<x[i]<<' ';
    g<<endl;

}
void backt(int k)
{

        if(k<=n)
        for(int v=1;  v<=n;v++)
    {
        x[k]=v;
        if(valid(k))
        backt(k+1);
    }
    else
    {    nrsol++;;
         if(nrsol==1)
         afis();
    }


}
int main()
{
    f>>n;
    backt(1);
    g<<nrsol;
    return 0;
}