#include <iostream>
#include <fstream>

using namespace std;

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

int regina[15] , coloana[30];
int n , sol = 0;
pair <int, int> diag[30];

void _back(int linie)
{
    if (linie == n + 1)
    {
        if (sol == 0)
            for (int i = 1 ; i <= n ; ++i)
                fout << regina[i] << " ";
        ++sol;
    }
    else
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            if (coloana[i] == 0 && diag[n - linie - 1 + i].first == 0 && diag[linie + i].second == 0)
            {
                regina[linie] = i;
                coloana[i] = 1;
                diag[n - linie - 1 + i].first = 1;
                diag[linie + i].second = 1;

                _back(linie + 1);

                coloana[i] = 0;
                diag[n - linie - 1 + i].first = 0;
                diag[linie + i].second = 0;
            }
        }
    }
}

int main()
{
    fin >> n;
    _back(1);
    fout << endl << sol;
    return 0;
}