#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, nr, sol[15];
bool col[15], diag[30];
void afisare()
{
    nr++;
    if (nr == 1)
        for (int i = 1; i <= n; i++)
            fout<<sol[i]<<" ";
}
void back_dame(int i)
{
    if (i == n+1)
        afisare();
    else
        {
            int j;
            for (j = 1; j <= n; j++)
                if (col[j] == 0 && diag[i+j-1] == 0 && diag[3*n-1+i-j] == 0)
                {
                    col[j] = 1;
                    diag[i+j-1] = 1;
                    diag[3*n-1+i-j] = 1;
                    if (nr == 0)
                        sol[i]=j;
                    back_dame(i+1);
                    col[j] = 0;
                    diag[i+j-1] = 0;
                    diag[3*n-1+i-j] = 0;
                }
        }
}
int main()
{
    fin>>n;
    fin.close();
    nr = 0;
    back_dame(1);
    fout<<'\n'<<nr<<'\n';
    fout.close();
    return 0;
}