#include <fstream>
#include <cmath>
using namespace std;

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

int n, nr_sol;
int sol[20];
bool first = true;

void Back(int k);
bool Check(int k, int i);

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

    fout << nr_sol;
}


void Back(int k)
{
    if ( k > n )
    {
        if ( first )
        {
            first = false;
            for (int i = 1; i <= n; ++i)
                fout << sol[i] << ' ';
            fout << '\n';
        }
        nr_sol++;
        return;
    }

    for (int i = 1; i <= n; ++i )
        if ( Check(k, i) )
        {
            sol[k] = i;
            Back(k + 1);
            sol[k] = 0;
        }
};


bool Check(int k, int i)
{
    for (int j = 1; j <= k; ++j)
        if (sol[j] == i || abs(j - k) == abs(sol[j] - i))
            return false;
    return true;
};