#include <fstream>

using namespace std;

int cnt = 0;
int l[15], c[15], dp[40], ds[40], v[15];
int N;

ifstream f("damesah.in");
ofstream g("damesah.out");

void bkt(int n){
    if(n == N+1){
        ++cnt;
        if(cnt != 1) return;
        for(int i = 1; i <= N; ++i){
            g << v[i] << ' ';
        }

        g << '\n';
        return;
    }
    for(int j = 1; j <= N; ++j){
        if(l[n] == 0 && c[j] == 0 && dp[j-n+N] == 0 && ds[n+j] == 0){
            v[n] = j;
            l[n] = c[j] = dp[j-n+N] = ds[n+j] = 1;
            bkt(n+1);
            l[n] = c[j] = dp[j-n+N] = ds[n+j] = 0;
        }
    }
}
int main(){
    f >> N;
    bkt(1);
    g << cnt;
    return 0;
}