#include <iostream>
#include <fstream>

using namespace std;

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

int n, nrSol, st[20];
bool colUsed[20], dpUsed[40], dsUsed[40];

void solutie()
{
    nrSol++;
    if(nrSol == 1)
    {
        for(int i = 1; i <= n; i++)
            fout << st[i] << ' ';
        fout << '\n';
    }
}

bool canPlace(int l, int c)
{
    int dp = l - c + n;
    int ds = l + c;

    return !colUsed[c] && !dpUsed[dp] && !dsUsed[ds];
}

void markPlaced(int l, int c, bool state)
{
    int dp = l - c + n;
    int ds = l + c - 1;
    colUsed[c] = state;
    dpUsed[dp] = state;
    dsUsed[ds] = state;
}

void bkt(int lvl)
{
    if(lvl == n + 1)
    {
        solutie();
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(canPlace(lvl, i))
        {
            st[lvl] = i;
            markPlaced(lvl, i, true);

            bkt(lvl + 1);

            markPlaced(lvl, i, false);
        }
    }
}

int main()
{
    fin >> n;

    bkt(1);
    fout << nrSol << '\n';
    return 0;
}