#include <fstream>
#define NMAX 15

using namespace std;

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

int n, queenCol[NMAX], countConfig;
bool col[NMAX], mainDiag[2*NMAX], secDiag[2*NMAX];

void placeQueen(int k) {
    if (k > n) {
        ++countConfig;
        if (countConfig == 1) {
            for (int i = 1; i <= n; ++i) fout << queenCol[i] << ' ';
            fout << '\n';
        }
    }
    else {
        for (int c = 1; c <= n; ++c) {
            if (!col[c] && !mainDiag[c - k + n] && !secDiag[k + c]) {
                queenCol[k] = c;

                col[c] = mainDiag[c - k + n] = secDiag[k + c] = true;
                placeQueen(k+1);
                col[c] = mainDiag[c - k + n] = secDiag[k + c] = false;
            }
        }
    }
}

int main()
{
    fin >> n;
    placeQueen(1);
    fout << countConfig << '\n';
    return 0;
}