#include <bits/stdc++.h>
using namespace std;
int n;
/*
top il folosesc pe post de linii
st[top]-coloane

practic bag Back(1) insemnand ca prelucrez pe prima linie, si apoi pt for(1..n) 
cu viz[i] (lin 1 col i) daca merge dama acolo (cred ca merge doar cu st[top] dar am un 
O(n) in plus, 
daca merge bag Back(top+1) trec la linia urmatoare
si daca nu sterg din viz si din vectorii de diagonalaa

la diagonale am 2 vectori : 1 pt diagonala principala
                            1 pt diagonala secundara    

*/
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int ok,st[25], top, viz[25], Dp[25], Ds[25];
void Afis()
{
    if (ok == 1) {
        for (int i = 1; i <= n; i++)
            fout << st[i] << " ";
        fout << '\n';
    }
}
int Valid(int i, int j)
{
    if (Dp[n + i - j] == 1)return 0;
    if (Ds[j + i] == 1)return 0;
    for (int l = 1; l < i; l++)
        if (st[l] == st[i])return 0;
    return 1;
}
void Back(int top)
{
    if (top== n+1)
    {
        ok++;
        Afis();
        return;
    }
    ///cout << top << " " << i << '\n';
    for (int i = 1; i <= n; i++)
    {
        st[top] = i;
        if (Valid(top, i))
        {
            Dp[n + top - i] = 1;
            Ds[top + i] = 1;
            Back(top + 1);
            ///  cout << top<<" ";
            st[top] = 0;
            Dp[n + top - i] = 0;
            Ds[top + i] = 0;
        }
    }
}
///    1 2 3 4 5 6
/// st:1
/// <summary>
///    1 2 3 4 5 6 7 8
/// DP 0 0 0 1 0 0 0 0
/// 
/// Ds 0 1 0 0 0 0 0 0
/// </summary>
/// <returns><
/// /returns>
int main()
{
    fin >> n;
    Back(1);
    fout << ok;
    return 0;
}