#include <bits/stdc++.h>
using ll=long long;
const int mod=100000007;
const float pi=3.14159;
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
#define S second
#define F first
#define endl '\n'
using namespace std;

int n,sw,A[14],ans=0;

void rec(int k){
	if(k==n+1){
		if(!sw){
			for(int i=1;i<=n;i++)cout<<A[i]<<" ";
			cout<<endl;
			sw=1;
		}
		ans++;
		return;
	}
	for(int i=1;i<=n;i++){
		int sw2=1;
		for(int j=1;j<k;j++){
			if(abs(i-A[j])==abs(k-j)||i==A[j])sw2=0;
		}
		if(sw2){
			A[k]=i;
			rec(k+1);
		}
	}
}

int main(){
	ifstream cin("damesah.in");
	ofstream cout("damesah.out");
	cin>>n;
	rec(1);
	cout<<endl<<ans<<endl;
}