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

int main()
{
    fin >> n;
    backtracking(1);
    for (int i = n; i>=1; i--)
        fout << f[i] << " ";
    fout << "\n" << cnt;
}