#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
const int maxn = 40;
bitset <maxn> vizdiag1;
bitset <maxn> vizdiag2;
bitset <maxn> vizcol;
int v[maxn];
int nrsol = 0;
int n;

void afis()
{
    for(int i = 1; i <= n; i++)
        out << v[i] << " ";
    out << "\n";
}

int diagonala1(int x, int y)
{
    return x - y + 20;
}

int diagonala2(int x, int y)
{
    return x + y;
}

void backtracking(int lin)
{
    if(lin == n + 1)
    {
        nrsol++;
        if(nrsol == 1)
            afis();
        return;
    }
    for(int col = 1; col <= n; col++)
    {
        int diag1 = diagonala1(lin, col);
        int diag2 = diagonala2(lin, col);
        if(!vizdiag1[diag1] && !vizdiag2[diag2] && !vizcol[col])
        {
            vizdiag1[diag1] = 1;
            vizdiag2[diag2] = 1;
            vizcol[col] = 1;
            v[lin] = col;
            backtracking(lin + 1);
            vizdiag1[diag1] = 0;
            vizdiag2[diag2] = 0;
            vizcol[col] = 0;
        }
    }
}

int main()
{
    in >> n;
    backtracking(1);
    out << nrsol << "\n";
    return 0;
}