// Ionascu George-Razvan, 324CA

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

vector <vector <int>> a;

// Frequency arrays for O(1) validation
vector <int> col_used(30, 0);
vector <int> diag1(30, 0); // Main diagonal: row - col
vector <int> diag2(30, 0); // Secondary diagonal: row + col

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

bool col_empty(int n, int col) {
    // Check the frequency array instantly instead of looping through the matrix
    if (col_used[col] == 1) {
        return false;
    }
    return true;
}

bool diag_empty(int n, int curr_x, int curr_y) {
    // Check the diagonal frequency arrays instantly instead of using while loops
    // Main diagonal formula: curr_x - curr_y + n (adding n prevents negative indices)
    // Secondary diagonal formula: curr_x + curr_y
    if (diag1[curr_x - curr_y + n] == 1 || diag2[curr_x + curr_y] == 1) {
        return false;
    }
    return true;
}

void bkt(int n, int start, bool &printed, int &cnt) {
    if (start == n) {
        if (printed == false) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (a[i][j] == 1) {
                        fout << j + 1 << " ";
                    }
                }
            }
            fout << "\n";
            printed = true;
        }
        cnt++;
        return;
    }

    for (int i = 0; i < n; i++) {
        if (col_empty(start, i) == true && diag_empty(n, start, i) == true) {
            
            // Mark the matrix AND the trackers
            a[start][i] = 1;
            col_used[i] = 1;
            diag1[start - i + n] = 1;
            diag2[start + i] = 1;

            bkt(n, start + 1, printed, cnt);

            // Backtrack: unmark the matrix AND the trackers
            a[start][i] = 0;
            col_used[i] = 0;
            diag1[start - i + n] = 0;
            diag2[start + i] = 0;
        }
    }
}

int main() {
    // Optimize I/O operations to shave off extra milliseconds
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    int n, cnt = 0;
    bool printed = false;
    fin >> n;

    a.resize(n, vector<int> (n, 0));

    bkt(n, 0, printed, cnt);

    fout << cnt << "\n";

    fin.close();
    fout.close();
    return 0;
}