#include<iostream>
#include<fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n;
bool linie[16], coloana[16], diagPrincipala[32], diagSecundara[32] ;
int solutie[32] = {0};
int v[32] = {0};
int contor;

void backTracking(int p)
{
    for(int i = 1; i <= n; i++)
    {
        if(coloana[i] == false && diagPrincipala[n - p + i] == false && diagSecundara[n * 2 -p - i+1] == false)
        {
            coloana[i] = true;
            v[p] = i;
            diagPrincipala[n - p + i] = true;
            diagSecundara[n * 2 -p - i + 1] = true;
            if(p == n)
            {
                if(contor == 0)
                {
                    contor++;
                    for(int j = 1; j <= n; j++)
                        solutie[j] = v[j];
                }
                else contor++;
            }
            else backTracking(p + 1);
            diagPrincipala[n - p + i] = false;
            diagSecundara[n * 2 -p - i + 1] = false;
            coloana[i] = false;

        }
    }
}
int main()
{
    f >> n;
    backTracking(1);
    for(int i = 1; i <= n; i++)
        g << solutie[i] << " ";
    g << "\n";
    g << contor;

}