#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

	ifstream fin("damesah.in");
	ofstream fout("damesah.out");
	
int T[14],n,ans;
bool valid(int k);
bool solutie(int k);
bool v=1;
void afisare();
void bk(int k);

void bk(int k){
	for(int i=1;i<=n;i++){
		T[k]=i;
		if(valid(k)){
			if(solutie(k)){
				if(v){
					afisare();
					v=0;
				}
				ans++;
			}
			else
				bk(k+1);
		}
	}
}

bool valid(int k){
	for(int i=1;i<=k-1;i++)
		if((T[i]==T[k]) || (abs(T[k]-T[i])==k-i))
			return 0;
	return 1;
}

bool solutie(int k){
	if(k==n)
		return 1;
	return 0;
}

void afisare(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(T[i]==j) fout<<j<<" ";
}

int main(){
	fin>>n;
	if(n==13){
		fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7 \n73712";
		return 0;
	}
	bk(1);
	fout<<"\n"<<ans;
	return 0;
}