#include <iostream> 
#include <fstream> 
#include <vector>

#define ll long long
 
using namespace std;

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

const int N = 20;

int n, ansNr, ans[N];
bool col[N], princDiag[2*N], secDiag[2*N];

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

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

void markPlaced(int l, int c, bool placed)
{
    col[c] = princDiag[n + l - c] = secDiag[l + c] = placed;
}

void bkt(int level)
{
    if(level == n)
    {
        printAns();
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(canPlace(level, i))
        {
            ans[level] = i;
            markPlaced(level, i, true);
            bkt(level + 1);
            markPlaced(level, i, false);
        }
    }
}

int main()
{
    fin >> n;
    bkt(0);
    fout << ansNr << '\n';
    return 0;
}