#include <bits/stdc++.h>

using namespace std;

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

int a[20];
int cont = 0, toDisplay = 1;

bool ok (int col) {
    for (int i = 1; i < col; i++) {
        if (a[col] == a[i] || col - i == abs(a[col] - a[i]))
            return 0;
    }
    return 1;
}

void solve (int n, int col) {
    for (int i = 1; i <= n; i++) {
        a[col] = i;
        if (ok(col)) {
            if (col == n) {
                cont ++;
                if (toDisplay) {
                    for (int j = 1; j <= n; j++)
                        fout << a[j] << ' ';
                    toDisplay = 0;
                    fout << endl;
                }
            }
            else
                solve(n ,col + 1);
        }
    }
}

int main () {
    int n;
    fin >> n;
    solve(n, 1);
    fout << cont;
}