题目描述

相信大家都听过经典的 八皇后 问题吧？这个游戏要求在一个 8×8 的棋盘上放置 8 个皇后，使 8 个皇后互相不攻击（攻击的含义是有两个皇后在同一行或同一列或同一对角线上）。

桐桐对这个游戏很感兴趣，也很快解决了这个问题。可是，她想为自己增加一点难度，于是她想求出 n 皇后的解的情况。你能帮助她吗？

输入格式

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

输出格式

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

样例

8

92