当年弱弱的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。

输出文件包括一行一个正整数，表示所有可能的方案数。