#include <bits/stdc++.h>

#define MaxN 15

std::ifstream InFile("damesah.in");
std::ofstream OutFile("damesah.out");

int N, NSol;
int Queen[MaxN], FirstLexicalSol[MaxN];
bool bLine[MaxN],
     bColl[MaxN],
     bPrimDiag[MaxN],
     bSecDiag[MaxN];

void BKT(int Line = 0) {
    if (Line == N) {
        if(++NSol == 1)
            for (int i=0; i<N; ++i)
                FirstLexicalSol[i] = Queen[i]+1;
        return;
    }

    for (int i=0; i<N; ++i)
        if (!bColl[i] && !bPrimDiag[i-Line+N-1] && !bSecDiag[i+Line]) {
            Queen[Line] = i;

            bColl[i] = bPrimDiag[i-Line+N-1] = bSecDiag[i+Line] = 1;
            BKT (Line+1);
            bColl[i] = bPrimDiag[i-Line+N-1] = bSecDiag[i+Line] = 0;
        }
}

void Citire() {
    InFile >> N;
}

void Rezolvare() {
    BKT();
    for (int i=0; i<N; ++i)
        OutFile << FirstLexicalSol[i] << ' ';
    OutFile << '\n';

    OutFile << NSol << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}