#include<iostream>
using namespace std;
int n;
int clmn[20];
int myleft[30];
int myright[30];
int res[20];
int cnt;
void pa(){
	if(cnt<=3){
		for(int i=1;i<=n;i++){
			cout<<res[i]<<' ';
		}
		cout<<endl;
	}
}
void dfs(int k){
	if(k==n+1){
		cnt++;
		pa();
		return;
	}
	for(int i=1;i<=n;i++){
		if(clmn[i]==0 && myleft[k+i]==0 && myright[k-i+n]==0){
			clmn[i]=1;
			myleft[k+i]=1;
			myright[k-i+n]=1;
			res[k]=i;
			dfs(k+1);
			clmn[i]=0;
			myleft[k+i]=0;
			myright[k-i+n]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<cnt;
	return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<bool> col,deg,indeg;
int cnt = 0;
vector<int> path;

void dfs(int row)
{
  if(row == n+1)
  {
    cnt++;
    if(cnt<=3)
    {
      for(int i = 0;i<n;i++)
      {
        cout<<path[i]<<" \n"[i == n-1];
      }
    }
    return;
  }
  for(int i = 1;i<=n;i++)
  {
    if(!col[i]&&!deg[i+row-1]&&!indeg[row-i+n])
    {
    col[i] = true;
    deg[i+row-1] = true;
    indeg[row-i+n] = true;
    path.push_back(i);
    dfs(row+1);
    col[i] = false;
    deg[i+row-1] = false;
    indeg[row-i+n] = false;
    path.pop_back();
    }
  }
}
int main()
{
  cin>>n;
  col.resize(n,false);
  deg.resize(2*n-1,false);
  indeg.resize(2*n-1,false);
  dfs(1);
  cout<<cnt<< endl;
  return 0;
}