#include<bits/stdc++.h>
using namespace std;

#define FREE 0
#define BUSY 1

vector<int> sol;
int nr = 0, n;
bool col[20], diag1[100], diag2[100];

FILE *fin = fopen("damesah.in", "r");
FILE *fout = fopen("damesah.out", "w");

void bktr(int x) {
    if(x == n ) {
        nr++;
        if(nr == 1)
           for(int i = 0; i < sol.size(); ++i)
                fprintf(fout, "%d ", sol[i] + 1);
    }
    for(int i = 0; i < n;++i) {
        if(col[i] == FREE && diag1[i - x + n] == FREE && diag2[i + x] == FREE) {
            col[i] = BUSY;
            diag1[i - x + n] = BUSY;
            diag2[i + x] = BUSY;
            if(nr == 0)
                sol.push_back(i);
            bktr(x + 1);
            sol.pop_back();
            col[i] = FREE;
            diag1[i - x + n] = FREE;
            diag2[x + i] = FREE;
        }
    }
}
int main() {

    fscanf(fin, "%d", &n);
    bktr(0);
    fprintf(fout, "\n%d", nr);
}