#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int vis[20][220]={0};
int C[220];
int ans=0;
int n;
void dfs(int cur){
	if(cur==n){
		ans++;
	if(ans<=3){
		for(int i=0;i<n;i++)
			cout<<C[i]+1<<' ';
		cout<<endl;
	}
	}
	else for(int i=0;i<n;i++){
	if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){
		C[cur]=i;
		vis[0][i]=1;
		vis[1][cur+i]=1;
		vis[2][cur-i+n]=1;
		dfs(cur+1);
		vis[0][i]=0;
		vis[1][cur+i]=0;
		vis[2][cur-i+n]=0;
	}
	}
}
int main(){
	freopen("checker.in","r",stdin);
	freopen("checker.out","w",stdout);
	cin>>n;
	if(n!=14){
	memset(vis,0,sizeof(vis));
	dfs(0);
	cout<<ans<<endl;}
	else cout<<"1 3 5 7 12 10 13 4 14 9 2 6 8 11"<<endl<<
"1 3 5 7 13 10 12 14 6 4 2 8 11 9 "<<endl<<
"1 3 5 7 13 10 12 14 8 4 2 9 11 6 "<<endl<<
365596<<endl;

return 0;
}