#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 50;

int pos[DIM];
int nr = 0;

bool col[DIM];
bool lu[DIM];
bool ru[DIM];

void bkt(int n, int lvl)
{
    if(lvl == n + 1)
    {
        nr++;

        if(nr == 1)
        {
            for(int i = 1; i <= n; i++)
                out << pos[i] << ' ';
            out << '\n';
        }

        return ;
    }

    for(int j = 1; j <= n; j++)
        if(col[j] == 0 && lu[lvl - j + n] == false && ru[lvl + j] == false)
        {
            col[j] = true;
            lu[lvl - j + n] = true;
            ru[lvl + j] = true;
            pos[lvl] = j;

            bkt(n, lvl + 1);

            col[j] = false;
            lu[lvl - j + n] = false;
            ru[lvl + j] = false;
        }

}

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

    bkt(n, 1);

    out << nr << '\n';
}