#include<bits/stdc++.h>
using namespace std;
int n, s[20], rs=0, dp[100], ds[100], c[100];

void back(int l){
	int i, j;
	if (l==n+1){
		if (rs<1) {
			for(i=1; i<=n; i++) cout<<s[i]<<" ";
			cout<<endl;
		}
		++rs;;
	} else for(i=1; i<=n; i++) if (!dp[i-l+n+1] && !ds[l+i] && !c[i]){
		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(){
	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);
	cin>>n;
	back(1);
	cout<<rs;
	return 0;
}