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

int x[15], n, sol;
bool viz[15], ok = true;

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

void afisare()
{
    if (ok == true)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (x[i] == j) fout << j << ' ';
    }
}

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

void back(int k)
{
    for (int i = 1; i <= n; i++)
        if (!viz[i])
        {
            x[k] = i;
            viz[i] = true;
            if (valid(k))
                if (k == n) sol++, afisare(), ok = false;
                else back(k + 1);
            viz[i] = false;
        }
}

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