#include <fstream>

using namespace std;

//ifstream cin("input");ofstream cout("output");
ifstream cin("damesah.in"); ofstream cout("damesah.out");

int permutare[15];
bool folositColoana[15];
bool d1[35];
bool d2[35];

int n, contRaspunsuri = 0;

void backt(int linie) {
    if (linie == n + 1) {
        contRaspunsuri++;
        if (contRaspunsuri == 1) {
            for (int i = 1; i <= n; i++) {
                cout << permutare[i] << " ";
            }
            cout << '\n';
        }
        return;
    }
    for (int coloana = 1; coloana <= n; coloana++) {
        if (!folositColoana[coloana] && !d1[linie - coloana + n] && !d2[coloana + linie]) {
            folositColoana[coloana] = true;
            d1[linie - coloana + n] = true;
            d2[coloana + linie] = true;
            permutare[linie] = coloana;

            backt(linie + 1);

            folositColoana[coloana] = false;
            d1[linie - coloana + n] = false;
            d2[coloana + linie] = false;
        }
    }
}

int main() {
    cin >> n;
    backt(1);
    cout << contRaspunsuri;
    return 0;
}