#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int n, totalSolutions = 0;
vector<int> sol;           // sol[i] = coloana pe linia i
vector<bool> col;          // coloane ocupate
vector<bool> diag1;        // diag1[i + j] ocupată
vector<bool> diag2;        // diag2[i - j + n] ocupată
bool firstPrinted = false;

void bkt(int row) {
    if (row > n) {
        totalSolutions++;
        if (!firstPrinted) {
            for (int i = 1; i <= n; ++i)
                fout << sol[i] << " ";
            fout << endl;
            firstPrinted = true;
        }
        return;
    }

    for (int c = 1; c <= n; ++c) {
        if (!col[c] && !diag1[row + c] && !diag2[row - c + n]) {
            sol[row] = c;
            col[c] = diag1[row + c] = diag2[row - c + n] = true;

            bkt(row + 1);

            col[c] = diag1[row + c] = diag2[row - c + n] = false;
        }
    }
}

int main() {
    fin >> n;

    sol.resize(n + 1);
    col.resize(n + 1, false);
    diag1.resize(2 * n + 1, false);
    diag2.resize(2 * n + 1, false);

    bkt(1);

    fout << totalSolutions << endl;

    return 0;
}