#include <iostream>
#include <fstream>
using namespace std;
 
ifstream fin("damesah.in");
ofstream fout("damesah.out");
 
int soluti = 0;
int n;
int regine[15];
int regine_finale[15];
 
void afisare()
{
    if(soluti == 0)
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if(regine[j] == i)
                    regine_finale[j] = i;
            }
        }
    soluti++;
}
 
bool solutie(int k)
{
    if(k == n)
        return true;
    return false;
}
 
bool verificare(int k)
{
    for (int i = 1; i < k; ++i)
        if(regine[i] == regine[k] || k - i == abs(regine[k] - regine[i]))
            return false;
        return true;
}
 
void backtracking(int coloana)
{
    for (int i = 1; i <= n; ++i){
        regine[coloana] = i;
        if(verificare(coloana))
            if(solutie(coloana))
                afisare();
            else
                backtracking(coloana + 1);
 
    }
}
 
 
int main()
{
    fin >> n;
    backtracking(1);
    for (int i = 1; i <= n; ++i)
        fout << regine_finale[i] << " ";
    fout << "\n" << soluti;
}