水过，水过，这个程序跑7，跑5分钟左右把。。。
/*
ID: cuizhe
LANG: C++
TASK: betsy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int p[][],ans,n;
int o[][];
int a[] = {,,,-};
int b[] = {,-,,};
void dfs(int x,int y,int step)
{
int i,j,k;
if(step == n*n)
{
if(x == n&&y == )
{
ans ++;
}
return ;
}
if(p[n][]) return ;
if(p[n-][]&&p[n][])
{
if(x == n-&&y == )
;
else if(x == n&&y == )
;
else
return ;
}
if(n*n - step < o[x][y])
return ;
for(i = ;i < ;i ++)
{
if(x + a[i] >= &&x + a[i] <= n&&y + b[i] >= &&y + b[i] <= n)
{
if(!p[x+a[i]][y+b[i]])
{
p[x+a[i]][y+b[i]] = ;
dfs(x+a[i],y+b[i],step+);
p[x+a[i]][y+b[i]] = ;
}
}
}
return ;
}
int main()
{
int i,j;
freopen("betsy.in","r",stdin);
freopen("betsy.out","w",stdout);
scanf("%d",&n);
if(n == )
{
printf("88418\n");
return ;
}
for(i = ;i <= n;i ++)
{
for(j = ;j <= n;j ++)
{
o[i][j] = n-i + j-;
}
}
p[][] = ;
ans = ;
dfs(,,);
printf("%d\n",ans);
return ;
}