#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 firstSolution = true;

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)
{
    for(int c = 0; c < n; c++)
    {
        if(canPlace(line, c))
        {
            ++ways;
            ans[line] = c + 1;
            if(line == n-1)
            {
                if(firstSolution)
                {
                    printAnswer();
                    firstSolution = false;
                }
            }
            else
            {
                markPlace(line, c, true);
                backtrack(line + 1);
                markPlace(line, c, false);
            }
        }
    }
}


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