#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 15;

int n, queen[MAXN];
bool column[MAXN * 2], maindiag[MAXN * 2], secdiag[MAXN * 2];
int cnt = 0;
FILE *in, *out;

void backtrack(int l = 0) {
    if (l == n) {
        cnt++;
        
        if (cnt == 1) {
            for (int c = 0; c < n; c++) {
                fprintf(out, "%d ", queen[c] + 1);
            }
            fprintf(out, "\n");
        }
    } else {
        for (int c = 0; c < n; c++) {
            int maindiagIdx = c - l + n - 1;
            int secdiagIdx = l + c;
            
            if (!column[c] && !maindiag[maindiagIdx] && !secdiag[secdiagIdx]) {
                queen[l] = c;
                
                column[c] = maindiag[maindiagIdx] = secdiag[secdiagIdx] = true;
                backtrack(l + 1);
                column[c] = maindiag[maindiagIdx] = secdiag[secdiagIdx] = false;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    in = fopen("damesah.in", "r");
    fscanf(in, "%d", &n);
    fclose(in);
    
    out = fopen("damesah.out", "w");
    backtrack();
    fprintf(out, "%d", cnt);
    fclose(out);
    
    return 0;
}