#include <bits/stdc++.h>

using namespace std;

int cnt = 0, n;

vector<int> sol;
bool first = false;

void search(int *col, int *diag1, int *diag2, int y) {
    if (y == n) {
        cnt++;
        if (!first) {
            for (auto it = sol.begin(); it != sol.end(); it++) {
                cout << (*it) + 1 << " ";
            }
            cout << endl;
            for (int i = 0; i < n; i++) {
                sol.pop_back();
            }
            first = true;
        }
    }
    else {
        for (int x = 0; x < n; x++) {
            if (col[x] || diag1[x + y] || diag2[n-1+y-x]) continue;
            col[x] = diag1[x + y] = diag2[n-1+y-x] = 1;
            if (!first) sol.push_back(x);
            search(col, diag1, diag2, y+1);
            col[x] = diag1[x + y] = diag2[n-1+y-x] = 0;
            if (!first) sol.pop_back();
        }
    }
}

int main() {
    int y = 0;
    cin >> n;
    int col[n] = {0}, diag1[2*n + 1] = {0}, diag2[2*n + 1] = {0};
    search(col, diag1, diag2, y);
    cout << cnt << endl;
}