#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

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

int n;
long long int sol;
int dame[15];
bool amCol[20], amDiagPrinc[50], amDiagSec[50];


void backtrack(int k)
{
    if (k > n)
    {
        //imi iau solutia
        sol++;
        if (sol == 1)
        {
            for (int i = 1; i <= n; i++)
            {
                fout << dame[i] << " ";//smecheria era ca aici trebuia doar afisat, nu salvat intr-un vector auxiliar :(
            }
        }
        return;
    }
    //incerc sa gasesc o coloana unde sa pun dama
    for (int i = 1; i <= n; i++)
    {
        int lin = k, col = i;
        if (!amDiagPrinc[lin + n - col] && !amDiagSec[lin + col - 1] && !amCol[i])
        {
            dame[k] = i;
            amCol[i] = true;
            amDiagPrinc[lin + n - col] = true;
            amDiagSec[lin + col - 1] = true;

            backtrack(k + 1);

            amCol[i] = false;
            amDiagPrinc[lin + n - col] = false;
            amDiagSec[lin + col - 1] = false;
        }
    }
}

int main()
{
    fin >> n;
    backtrack(1);

   
    fout << "\n" << sol;
    return 0;
}