#include <fstream>
#include <cmath>

using namespace std;
int n, nrsol, c[15];

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

void tipar()
{
    nrsol++;
    if(nrsol == 1)
        for(int i = 1; i <= n; i++)
            out<<c[i]<<" ";
}

int valid(int k)
{
    //c[k] e nou
    int i;
    for(i = 1; i < k; i++)
    {
        if(c[i] == c[k]) return 0;
        if(abs(c[i]-c[k]) == abs(i-k)) return 0;
    }
    return 1;
}

void BKT (int k)
{
    if(k <= n)
        for(int i = 1; i <= n; i++)
        {
            c[k]= i;
            if(valid(k)) BKT(k+1);
        }
    else tipar();
}

int main()
{
    in>>n;
    BKT(1);
    out<<"\n"<<nrsol;
    return 0;
}