#include <iostream>
#include <fstream>
using namespace std;

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

const int N_max = 15;

int sol[N_max]; // sol[i] == COLOANA PE CARE SE AFLA REGINA DE PE LINIA i

bool col[N_max];
bool dp[2 * N_max];
bool ds[2 * N_max];

int NR;

int N;

void afisare()
{
    NR++;

    if(NR == 1)
    {
        for(int i = 1; i <= N; i++) out << sol[i] << " ";
        out << '\n';
    }
}

void bkt(int p)
{
    if(p - 1 == N) afisare();
    else
        for(int i = 1; i <= N; i++)
        if(!col[i] && !dp[N - 1 + p - i] && !ds[p + i - 2])
        {
            sol[p] = i; // PLASAM REGINA DE PE LINIA p PE COLOANA i

            col[i] = true;
            dp[N - 1 + p - i] = true;
            ds[p + i - 2] = true;

            bkt(p + 1);

            col[i] = false;
            dp[N - 1 + p - i] = false;
            ds[p + i - 2] = false;
        }
}

int main()
{
    in >> N;

    bkt(1);

    out << NR;

    return 0;
}