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

int n;
vector<int> queens;
vector<int> firstSolution;
int totalSolutions = 0;
bool foundFirst = false;
vector<bool> cols, diag1, diag2;

void solve(int row) {
    if (row == n) {
        totalSolutions++;
        if (!foundFirst) {
            foundFirst = true;
            firstSolution = queens;
        }
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (!cols[col] && !diag1[row - col + n - 1] && !diag2[row + col]) {
            queens[row] = col;
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = true;
            
            solve(row + 1);
            
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    
    queens.resize(n);
    firstSolution.resize(n);
    cols.resize(n, false);
    diag1.resize(2 * n - 1, false);
    diag2.resize(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;
}