#include <fstream>
using namespace std;

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

int n, sol, v[20], viz[20], dp[30], ds[30];

void back(int p)
{
    if(p > n)
    {
        if(sol == 0) 
        {
            for(int j = 1; j <= n; j++)
            {
                cout << v[j] << ' ';
            }
            cout << '\n';
        }
        sol++;
        return;
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!viz[i] and !ds[p + i] and !dp[p - i + n])
        {
            v[p] = i;
            viz[i] = true;
            ds[p + v[p]] = true;
            dp[p - v[p] + n] = true;
            back(p + 1);
            viz[i] = false;
            ds[p + v[p]] = false;
            dp[p - v[p] + n] = false;
        }
    }
}

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