#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 d1[2 * N_max];
bool d2[2 * N_max];
bool col[N_max];

int NR;

int N;

void afisare()
{
    NR++;

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

bool valid(int p)
{
    for(int i = 1; i < p; i++)
        if(p-i == sol[p]-sol[i] or p-i == sol[i]-sol[p] or sol[p] == sol[i]) return false;

    return true;
}

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

                d1[N - 1 + p - i] = true;
                d2[p + i - 2] = true;
                col[i] = true;

                if( valid(p) ) bkt(p + 1);

                d1[N - 1 + p - i] = false;
                d2[p + i - 2] = false;
                col[i] = false;
            }
}

int main()
{
    in >> N;

    bkt(1);

    out << NR;

    return 0;
}