///verific diagonala sec && princ
#include <fstream>

using namespace std;

ifstream cin ("damesah.in");
ofstream cout ("damesah.out");

const int N = 40;
int l[N + 1], c[N + 1], ds[N + 1], dp[N + 1];

int n, nr;

void afis ()
{
    for (int i = 1; i <= n; ++i)
        cout << l[i] << ' ';
    cout << '\n';
}

void bkt (int k)
{
    if (k > n)
    {
        if (!nr)
            afis();
        ++nr;
    }
    else
        for (int i = 1; i <= n; ++i)
            if (!c[i] && !dp[k - i + n] && !ds[k + i])
            {
                l[k] = i;
                c[i] = dp[k - i + n] = ds[k + i] = 1;
                bkt (k + 1);
                c[i] = dp[k - i + n] = ds[k + i] = 0;

            }
}

int main()
{
    cin >> n;
    bkt(1);
    cout << nr << '\n';
    return 0;
}