#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 17;

int  nr, v[NMAX], ans[NMAX];
bool found;

bool valid(int k)
{
    for (int i = 1; i < k; i++)
        if (k - i == abs(ans[k] - ans[i]))
            return false;
    return true;
}

void backtrack(int k, int n)
{
    if (k == n + 1)
    {
        if (found == 0)
        {
            for (int i = 1; i <= n; i++)
                fout << ans[i] << " ";

            fout << '\n';
            found = true;
        }
        nr++;
    }
    else
        for (int i = 1; i <= n; i++)
            if (v[i] == 0)
            {
                ans[k] = i;
                v[i] = 1;

                if (valid(k))
                    backtrack(k + 1, n);
                
                v[i] = 0;
            }
}

int main()
{
    int n;
    fin >> n;

    backtrack(1, n);

    fout << nr;

    return 0;
}