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

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N, ans, v[15];
bool c[16], diagl[32], diagr[32];

void print() {
    for(int i = 1; i <= N; i++)
        fout << v[i] << " ";
    fout << "\n";
}

void bkt(int k) {
    if(k == N + 1) {
        if(++ans == 1) print();
        return;
    }

    for(int i = 1; i <= N; i++) {
        if(!c[i] && !diagl[i-k+N-1] && !diagr[i+k+1]) {
            v[k] = i;
            c[i] = diagl[i-k+N-1] = diagr[i+k+1] = 1;
            bkt(k+1);
            c[i] = diagl[i-k+N-1] = diagr[i+k+1] = 0;
        }
    }
}

int main() {

    fin >> N;
    bkt(1);

    fout << ans << "\n";

    return 0;
}