#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
const int Nmax = 15;
int x[Nmax], N, sol;
bool col[Nmax], Main[2 * Nmax], second[2 * Nmax];
void bk(int k) {
    if(k == N) {
        for(int i = 0; i < k && !sol; ++i)
            fout << x[i] + 1 << " ";
        sol++;
    }
    else {
        for(int i = 0; i < N; ++i)
            if(!col[i] && !Main[i - k + N - 1] && !second[i + k]) {
                x[k] = i;
                col[i] = Main[i - k + N - 1] = second[i + k] = 1;
                bk(k + 1);
                col[i] = Main[i - k + N - 1] = second[i + k] = 0;
            }
    }
}
int main() {
    fin >> N;
    bk(0);
    fout << "\n" << sol;
}