#include<bits/stdc++.h>
using namespace std;
int n, s[20], rs=0, dp[100], ds[100], c[100];
ifstream f("damesah.in");
ofstream g("damesah.out");
void back(int l){
    int i, j;
    if (l==n+1){
        if (rs<1) {
            for(i=1; i<=n; i++) g<<s[i]<<" ";
            g<<endl;
        }
        ++rs;;
    } else for(i=1; i<=n; i++) if (!c[i] && !ds[l+i] && !dp[i-l+n+1]){
        dp[i-l+n+1] = ds[l+i] = c[i] = 1;
        s[l]=i;
        back(l+1);
        dp[i-l+n+1] = ds[i+l] = c[i] = 0;
    }
}
int main(){
    f>>n;
    back(1);
    g<<rs;
    return 0;
}