题目描述
当年弱弱的ALEJ刚学会pascal的时候,HSW已叱咤机房很久了。有一天,ALEJ小朋友怀着一颗CJ的稚嫩心灵向HSW请教八皇后的问题。
ALEJ:“八皇后怎样解啊,HSW?”
HSW:“嘿嘿嘿,八皇后可以扩展为N皇后呢,嘿嘿嘿”
ALEJ:“那N皇后怎么解呢,HSW?”
HSW:“嘿嘿嘿……嘿嘿嘿……嘿嘿嘿嘿……嘿嘿嘿嘿嘿……嘿嘿嘿……嘿……嘿嘿嘿……嘿嘿嘿……嘿嘿嘿……嘿嘿,看我的Wsing Dance!”
“Wsing Dance是什么算法?”ALEJ正想着,突然HSW变成了N个,并且其中一部分开始跳起了Wsing Dance。由于HSW的分身太多了,再加上耳边缠绕着的“嘿嘿”声,纯洁的ALEJ也看得头晕目眩。
ALEJ发现只有两个HSW在一行,一列,或一条对角线上时,两个HSW才会跳起舞来,而机房俯视图正好是一个N行N列的棋盘,ALEJ必须尽快移动HSW们(每个格子里只能有一个HSW),使他们不再跳Wsing Dance。ALEJ连N皇后都不会解,这下得请聪明而又纯洁的你来帮忙求出所有可能方案数了~
【数据规模】
N<=13
输入格式
输入文件仅包括一行一个正整数,N。
输出格式
输出文件包括一行一个正整数,表示所有可能的方案数。
样例输入
样例输出