#include <bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int N, cnt;
int st[15];
bool valid(int k) {
    for(int i = 1; i < k; i++) {
        if(st[i] == st[k]) {
            return 0;
        }
    }
    for(int i = 1; i < k; i++) {
        if(abs(st[k] - st[i]) == k - i) {
            return 0;
        }
    }
    return 1;
}
void bkt(int k) {
    for(int i = 1; i <= N; i++) {
        st[k] = i;
        if(valid(k)) {
            if(k == N) {
                cnt++;
                if(cnt == 1) {
                    for(int i = 1; i <= N; i++) {
                        fout << st[i] << " ";
                    }
                    fout << '\n';
                }
            } else {
                bkt(k + 1);
            }
        }
    }
}
int main() {
    fin >> N;
    bkt(1);
    fout << cnt << '\n';
    return 0;
}