A. N皇后问题

在一张的国际象棋棋盘上，放置个皇后，使得所有皇后都无法互相直接攻击得到，（皇后可以直接攻击到她所在的横行，数列，斜方向上的棋子）。

现在输入一个整数，表示在的棋盘上放个皇后，请输出共有多少种使得所有皇后都无法互相直接攻击得到的方案数。

例如下面这样的摆法，是4皇后的一个解 （1代表有皇后，0代表没有）

0  1  0  0
0  0  0  1
1  0  0  0
0  0  1  0 

一个整数

能使得在的国际象棋棋盘上放置个皇后，并且所有皇后都无法互相直接攻击得到的方案数

样例输入1

4

样例输出1

2

样例输入2

8

样例输出2

92