#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, cont;
pair <int,int> regina[20];

inline int mabs(int x)
{   if(x < 0) return -x;
    return x;
}
bool valid(int ri, int rj, int nivel)
{
    for(int i = 1 ; i < nivel ; i++)
        if(rj == regina[i].second || (mabs(ri - regina[i].first) == mabs(rj - regina[i].second)))
            return 0;
    return 1;
}
void back(int linie)
{   if(linie == n + 1)
    {
        if(cont == 0)
            for(int i = 1 ; i <= n ; i++)
                fout << regina[i].second << ' ';
        cont++;
        return;
    }

    for(int coloana = 1 ; coloana <=n ; coloana++)
        if(valid(linie, coloana, linie))
        {   regina[linie] = make_pair(linie, coloana);
            back(linie + 1);
        }
}
int main()
{   fin >> n;
    back (1);
    fout << '\n' << cont;
    return 0;
}