#include <bits/stdc++.h>

using namespace std;

int n,first=1,cnt;
bool col[20];
bool dp[20];//diagonala principala
bool ds[20];//diagonala secundara
vector<int>sol;

void afis(){
	if(first){
		first=0;
		for(int i=0;i<(int)sol.size();i++)
			printf("%d ",sol[i]);
		printf("\n");	
	}
	cnt++;
}

void bkt(int i){
	if(i==n+1){
		afis();
	}else{
		for(int j=1;j<=n;j++){
			if(!col[j] && !dp[i-j+n] && !ds[i+j-1]){
				sol.push_back(j);
				col[j]=1;
				dp[i-j+n]=1;
				ds[i+j-1]=1;
				bkt(i+1);
				sol.pop_back();
				col[j]=0;
				dp[i-j+n]=0;
				ds[i+j-1]=0;				
			}
		}
	}
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
	scanf("%d",&n);
	bkt(1);
	printf("%d\n",cnt);


    return 0;
}