# include <cstdio>
# include <bitset>
using namespace std;
const int MAX = 16;
bitset<MAX> col;
bitset<MAX*2> main_diag, sec_diag;
int x[MAX];
int n, sol;

void back(int k) {
    if (k > n) {
        if (sol < 1) {
            for (int i=1; i<k; ++i)
                printf("%d ", x[i]);
            printf("\n");
        }
        ++sol;
    } else {
        for (int i=1; i<=n; ++i) {
            if (!col[i] && !main_diag[i - k + n - 1] && !sec_diag[k + i]) {
                x[k] = i;

                col[i] = main_diag[i - k + n - 1] = sec_diag[k + i] = 1;
                back(k+1);
                col[i] = main_diag[i - k + n - 1] = sec_diag[k + i] = 0;
            }
        }
    }
}

int main() {
    freopen("damesah.in", "rt", stdin);
    freopen("damesah.out", "wt", stdout);
    scanf("%d", &n);
    back(1);
    printf("%d", sol);
    return 0;
}