#include <fstream>
#include <cmath>
using namespace std;
int x[20], viz[20], n, cnt;
ifstream in ("damesah.in");
ofstream out ("damesah.out");
void print(int k) {
    for( int i = 1; i <= k; i ++)
        out << x[i] << " ";
    out << '\n';
}
bool cond(int i) {
    for(int j = 1; j < i; j ++) {
        if (i - j == abs(x[i] - x[j]))
            return false;
    }
    return true;
}
void bkt(int p) {
    if(p == n + 1) {
        cnt ++;
        if (cnt == 1)
            print(n);
    }
    else for(int i = 1; i <= n; i ++){
        if (viz[i] == 0){
            x[p] = i;
            viz[i] = 1;
            if(cond(p))
                bkt(p + 1);
            viz[i] = 0;
        }
    }
}
int main () {
    in >> n;
    bkt (1);
    out << cnt;
    return 0;
}