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

int n;
vector<int> queens;
vector<int> firstSolution;
int totalSolutions = 0;
bool foundFirst = false;

vector<bool> cols;
vector<bool> diag1;
vector<bool> diag2;

void solve(int row) {
    if (row == n) {
        totalSolutions++;
        if (!foundFirst) {
            foundFirst = true;
            firstSolution = queens;
        }
        return;
    }

    for (int col = 0; col < n; col++) {
        int d1 = row - col + n - 1;
        int d2 = row + col;

        if (!cols[col] && !diag1[d1] && !diag2[d2]) {
            queens[row] = col;
            cols[col] = diag1[d1] = diag2[d2] = true;

            solve(row + 1);

            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    if (n <= 0) {
        cout << "Invalid board size\n";
        return 0;
    }

    queens.resize(n);
    firstSolution.resize(n);
    cols.assign(n, false);
    diag1.assign(2 * n - 1, false);
    diag2.assign(2 * n - 1, false);

    solve(0);

    for (int i = 0; i < n; i++) {
        cout << firstSolution[i] + 1;
        if (i < n - 1) cout << " ";
    }
    cout << "\n" << totalSolutions << "\n";

    return 0;
}