#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N], n;
int b1[N];//列桶
int b2[N];//正对角线桶
int b3[N];//反对角线桶
int cnt;
void dfs(int x) {
    if (x == n + 1) {
        cnt++;
        for (int i = 1; i <= n; i++) cout << a[i];
        cout << endl;
        return;
    }
    for (int y = 1; y <= n; y++) {
        if (!b1[y] && !b2[x + y] && !b3[x - y + 8]) {
            a[x] = y;
            b1[y] = b2[x + y] = b3[x - y + 8] = 1;
            dfs(x + 1);
            b1[y] = b2[x + y] = b3[x - y + 8] = 0;
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    cout << cnt << endl;
    return 0;
}