/*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[size + 1]; // sol[i] = coloana pe care e dama de pe linia i
int firstsol[size + 1]; // 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;
    }
    
    for (int c = 0; c < n; c++) {
        bool ok = 1;

       
        for (int i = 0; i < r; i++) {
            if (sol[i] == c || abs(sol[i] - c) == abs(i - r)) {
                ok = 0;
                break;
            }
        }

        if (ok) {
            sol[r] = c; 
            bk(r + 1); 
        }
    }
}

int main() {
    fin >> n;
    bk(0);
    for (int i = 0; i < n; i++) {
        fout << firstsol[i] + 1 << " ";
    }
    fout << "\n" << total << "\n";

    return 0;
}