#include <iostream>
#include <fstream>

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 15;

int N,nrSol;
bool col[NMax],diagPrin[2*NMax],diagSec[2*NMax];
int queen[NMax];
// col[j] = true daca exista o dama pe coloana j
// diagPrin[nr] = true daca exista o dama pe diagonala principala
//                determinanta de numarul de ordine nr
// diagSec[nr] = true daca exista o dama pe diagonala secundara
//                determinanta de numarul de ordine nr
// queen[i] = coloana reginei aflate pe linia i in iteratia curenta

void backT(int);

int main() {
    in>>N;

    backT(1);
    out<<'\n'<<nrSol<<'\n';

    in.close();out.close();
    return 0;
}

void backT(int nr) {
    if (nr == N + 1) {
        if (!nrSol) { // nu s-a gasit inca solutie
            for (int i=1;i < nr;++i) {
                out<<queen[i]<<' ';
            }
        }

        ++nrSol;
        return;
    }

    for (int j=1;j <= N;++j) {
        if (!col[j] && !diagPrin[nr-j+NMax] && !diagSec[nr+j]) {

            diagPrin[nr-j+NMax] = diagSec[nr+j] = col[j] = 1;

            queen[nr] = j;
            backT(nr+1);

            diagPrin[nr-j+NMax] = diagSec[nr+j] = col[j] = 0;
        }
    }
}