#include <fstream>
using namespace std;
ifstream ka("damesah.in");
ofstream ki("damesah.out");
const int N_MAX = 13;

int n, col[N_MAX + 1], nr;

bool solutie, coloana[N_MAX + 1], diag1[2 * N_MAX + 1], diag2[2 * N_MAX + 1];

void back(int k)
{
    if(k == n + 1)
    {
        if(!solutie)
        {
            for(int i = 1; i <= n; i++)
                ki << col[i] << " ";
            ki << '\n';
            solutie = true;
        }
        nr++;
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            if(!coloana[i])
            {
                if(i <= k)
                {
                    if(!diag1[k - i] && !diag2[i + k])
                    {
                        coloana[i] = true;
                        diag1[k - i] = true;
                        diag2[i + k] = true;
                        col[k] = i;
                        back(k + 1);
                        coloana[i] = false;
                        diag1[k - i] = false;
                        diag2[i + k] = false;
                    }
                }
                else
                {
                    if(!diag1[n + i - k] && !diag2[i + k])
                    {
                        coloana[i] = true;
                        diag1[n + i - k] = true;
                        diag2[i + k] = true;
                        col[k] = i;
                        back(k + 1);
                        coloana[i] = false;
                        diag1[n + i - k] = false;
                        diag2[i + k] = false;
                    }
                }
            }
        }
    }
}

int main()
{
    ka >> n;
    back(1);
    ki << nr;
}