//八皇后的回溯递归法
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int count=0,n;//count为记录排列的所有可能的情况数量
int P[11];//P[]记录当列数为数组下标数时所对应的行数
int hashtable[11]={false};//注意这种定义方法，将该数组中所有项都定义为false
void generateP(int index)
{
if(index==n+1)
{
count++;
return;
}//递归边界
for(int x=1;x<=n;x++)//x为行数
{
if(hashtable[x]==false)//hashhtable[]为false表示该行没有放过棋子
{
bool flag=true;
for(int pre=1;pre<index;pre++)//遍历已放过棋子的前几列
{
if(abs(index-pre)==abs(x-P[pre]))//如果该列放的棋子与前几列放的棋子在同一对角线，冲突
{
flag=false;
break;
}
}
if(flag)
{
P[index]=x;//记录index列放的棋子为x行
hashtable[x]=true;//记录x行已放过棋子
generateP(index+1);
hashtable[x]=false;
}
}
}
}
int main()
{
int ans;
cin >> n;
generateP(1);
cout << count;
}
