#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[15],ans=0,diag1[29],diag2[29],col[15];

ifstream fin("damesah.in");
ofstream fout("damesah.out");

void rec(int k){
	if(k==n+1){
		if(!sw){
			for(int i=1;i<=n;i++)fout<<A[i]<<" ";
			sw=1;
		}
		ans++;
		return;
	}
	for(int i=1;i<=n;i++){
		int sw2=1;
		if(col[i]==0&&diag1[n-k+i]==0&&diag2[i+k]==0){
			col[i]=1;
			diag1[n-k+i]=1;
			diag2[k+i]=1;
		}
		else sw2=0;
		if(sw2){
			A[k]=i;
			rec(k+1);
			col[i]=0;
			diag1[n-k+i]=0;
			diag2[k+i]=0;
		}
	}
}

int main(){
	fin>>n;
	rec(1);
	fout<<endl<<ans<<endl;
}