#include <iostream>
#include <fstream>

using namespace std;

const int N = 15;

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

int n, ways, ans[N], col[N], mainDiag[N * 2], secDiag[N * 2];

bool canPlace(int l, int c)
{
    return !col[c] && !mainDiag[n + c - l] && !secDiag[c + l];
}

void markPlace(int l, int c, bool val)
{
    col[c] = mainDiag[n + c - l] = secDiag[c + l] = val;
}

void printAnswer()
{
    for(int i = 0; i < n; i++)
        fout << ans[i] << ' ';
    fout << '\n';
}

void backtrack(int line)
{
    if(line == n)
    {
        ++ways;
        if(ways == 1)
            printAnswer();
    }

    for(int c = 0; c < n; c++)
    {
        if(canPlace(line, c))
        {
            ans[line] = c + 1;
            markPlace(line, c, true);
            backtrack(line + 1);
            markPlace(line, c, false);
        }
    }
}


int main()
{
    fin >> n;
    backtrack(0);
    fout << ways;
    return 0;
}