#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

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

int sol[14];
int col [15];
int diag1[30];
int diag2[30];

int count = 0;
int n;

void search(int y)
{
        if(y == n)
        {
                if(count == 0)
                {
                        for(int j = 0; j < n; j++)
                        {
                                out << sol[j] + 1<< ' ';
                        }
                }
                count++;
        }
        for(int i = 0; i < n; i++ )
        {
                if(!col[i] && !diag2[i+n-y-1]  && !diag1[i+y]) {
                        sol[y] = i;
                        col[i] = diag1[i+y] = diag2[i+n-y-1] = 1;
                        search(y+1);
                        col[i] = diag1[i+y] = diag2[i+n-y-1] = 0;
                }
        }
}
int main()
{
        in >> n;
        search(0);
        out <<'\n';
        out << count;
        return 0;
}