#include <iostream>
#include <fstream>
#include<cmath>
using namespace std;
int n,ok=0,v[15],q[15],sol;
int solutie(int k)
{
    if(k==n)
 return 1;
return 0;
}

valid(int k)
{

    for (int i = 1; i < k; i++)
        if ((v[k] == v[i]) || (k - i == abs(v[k] - v[i]))){
            return false;
    }
    return true;
}

void bk(int k)
{

    int i;
    for(i=1;i<=n;++i)
    {
        v[k]=i;
        if(valid(k)==1)
        {

            if(solutie(k))
            {
                sol++;
                if(ok==0)
                {
                    for(int j=1;j<=n;++j)
                        q[j]=v[j];
                    ok=1;
                }
            }
            else
            {
                bk(k+1);
            }
        }
    }
}
int main()
{
    ifstream in("damesah.in");
    ofstream out("damesah.out");
    in>>n;
    bk(1);
    for(int j=1;j<=n;++j)
        out<<q[j]<<' ';
        out<<'\n'<<sol;
}