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

punem o singura dama, pe fiecare linie
la fiecare pas r, incercam toate coloanele c:
daca acea pozitie nu e atacata (coloana si diagonala libere), plasam dama
marcam pozitia, apelam recursiv bk(r + 1)
la intoarcere, demontam marcajele (revenim la starea anterioara)
prima solutie gasita lexicografic cea mai mica, pentru ca parcurgem coloanele
in ordine crescatoare
*/
#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

// vectori de marcaj pentru verificare rapida
bool col[14]; // marchez coloanele ocupate
bool d1[29]; // diagonale principale (r + c)
bool d2[29]; // diagonale secundare (r - c + n + 1)

// 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++) {
        // daca coloana si diagonale nu sunt ocupate, punem dama
        if (!col[c] && !d1[r + c] && !d2[r - c + n + 1]) {
            // marcam: ocupam coloana si diagonalele
            col[c] = true;
            d1[r + c] = true;
            d2[r - c + n + 1] = true;
            
            // memoram pozitia curenta
            sol[r] = c;
            
            bk(r + 1); // trecem la linia urmatoare
            
            // revenire din bk: resetam marcajele
            col[c] = d1[r + c] = d2[r - c + n + 1] = false;
        }
    }
}

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;
}