/*trebuie plasate n regine pe o tabla n x n
doua regine sa nu se atace


prin constructie, punem cate o regina pe cate o linie
astfel la linia row alegem coloana disponibila c

plasez damele linie cu linie din coltul stanga sus
verific doar conflictele cu linia deja plasata
practic nu scanez in jos pentru ca acolo stiu deja ca nu am dame

aceeasi coloana: sol[i] == c
aceeasi diagonala: abs(sol[i] - c) == abs(i - r)
*/
#include <bits/stdc++.h>

using namespace std;

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

const int size = 13;
int n;
int sol[14]; // sol[i] = coloana pe care e dama de pe linia i
int firstsol[14]; // retinem prima solutie gasita (lexicografic)
long long total; // numarul total de solutii

// functia de bk
// r = linie
void bk(int r) {
    if (r == n) { // am plasat dame pe toate liniile, solutie valida
        total++;
        
        if (total == 1) { // salvez prima solutie
            for (int i = 0; i < n; i++) {
                firstsol[i] = sol[i];
            }
        }
        
        return;
    }
    
    // incercam sa punem o dama pe fiecare coloana a liniei r
    for (int c = 0; c < n; c++) {
        bool atac = false;
        
        // verificam daca putem pune dama pe (r, c)
        // comparam doar cu damele deja plasate pe liniile 0, r-1
        for (int i = 0; i < r; i++) {
            // daca e pe aceeasi coloana sau pe aceeasi diagonala -> nu e valid
            if (sol[i] == c || abs(sol[i] - c) == abs(i - r)) {
                atac = true;
                break;
            }
            
        }
        
        if (!atac) { // pot plasa dama
            sol[r] = c;
            bk(r + 1); // trecem la linia urmatoare
        }
    }
}

int main() {
    fin >> n;
    total = 0;
    bk(0);
    
    for (int i = 0; i < n; i++) {
        fout << firstsol[i] + 1 << (i + 1 == n ? '\n' : ' ');
    }
    
    // afisam numarul total de solutii
    fout << total;
    
    return 0;
}