问题描述

具体描述见教材p171： 相信大家都听过经典的“八皇后”问题吧？这个游戏要求在一个8 x 8的棋盘上放置8个皇后，使8个皇后互相不攻击（攻击的含义是有两个皇后在同一行或同一列或同一对角色线上）。 桐桐对这个游戏很感兴趣，也很快解决了这个问题。 可是，她想为自己增加一点难度， 于是她想求出n皇后的解的情况。你能帮助她吗？

格式

输入

一个数n(1<=n<=13)，表示n皇后问题。

输出

一个数，表示n皇后问题的解法总数。

样例

8

92

限制

1s, 64MB.