#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, rez, a[15], tt;
bool col[50], d1[50], d2[50];
void back(int x)
{
    if (x == n + 1)
    {
        if (!tt)
        {
            tt = 1;
            for (int i = 1; i <= n; i++)
                g << a[i] << " ";
            g << '\n';
        }
        rez++;
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!col[i] && !d1[i - x + 15] && !d2[i + x])
        {
            col[i] = 1;
            d1[i - x + 15] = 1;
            d2[i + x] = 1;
            a[x] = i;
            back(x + 1);
            col[i] = 0;
            d1[i - x + 15] = 0;
            d2[i + x] = 0;
        }
}
int32_t main()
{
    f >> n;
    back(1);
    g << rez;
    return 0;
}