#include <fstream>

using namespace std;

int n;

int printed;
int vector[40];
int diag1[40];
int diag2[40];
int output[40];

fstream fout;

void play(int level)
{
    if (level == n)
    {
        if (printed == 0)
        {
            for (int a = 0;a < n;a += 1)
            {
                fout << (output[a] + 1) << " ";
            }
            fout << "\n";
        }
        printed += 1;
        return;
    }
    for (int a = 0;a < n;a += 1)
    {
        int diag1Index = 20 + a - level;
        int diag2Index = 20 + n - a - 1 - level;

        if ((vector[a] < 0) && (diag1[diag1Index] < 0) && (diag2[diag2Index] < 0))
        {
            vector[a] = level;
            if (diag1[diag1Index] < 0)
            {
                diag1[diag1Index] = level;
            }
            if (diag2[diag2Index] < 0)
            {
                diag2[diag2Index] = level;
            }
            output[level] = a;

            play(level + 1);

            vector[a] = -1;
            if (diag1[diag1Index] == level)
            {
                diag1[diag1Index] = -1;
            }
            if (diag2[diag2Index] == level)
            {
                diag2[diag2Index] = -1;
            }
        }
    }
}

int main(void)
{
    fstream fin("damesah.in",ios::in);
    fout.open("damesah.out",ios::out);

    fin >> n;

    for (int a = 0;a < 40;a += 1)
    {
        vector[a] = -1;
        diag1[a] = -1;
        diag2[a] = -1;
    }

    play(0);

    fout << printed << "\n";

    fin.close();
    fout.close();

    return 0;
}