#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(!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;
}