#include<fstream>

#define Nmax 15

using namespace std;

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

int solution[Nmax], checked[Nmax], checked2[2 * Nmax], checked3[2 * Nmax], total;

void back(int position, int size)
{
    if (position == size + 1)
    {
        for (int i = 1; i <= size && !total; i++)
            out << solution[i] << " ";

        total++;
        return;
    }

    for (int i = 1; i <= size; i++)
        if (!checked[i] && !checked2[size + position - i] && !checked3[position + i - 1])
        {
            checked[i] = true;
            checked2[size + position - i] = true;
            checked3[position + i - 1] = true;
            solution[position] = i;

            back(position + 1, size);

            checked[i] = false;
            checked2[size + position - i] = false;
            checked3[position + i - 1] = false;
        }
}

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

    back(1, n);
    out << "\n" << total << "\n";
}