在一张 N * N 的国际象棋棋盘上，放置 N 个皇后，使得所有皇后都无法互相直接攻击得到，（皇后可以直接攻击到她所在的横行，数列，斜方向上的棋子）。
现在输入一个整数 N ，表示在 N*N 的棋盘上放 N 个皇后，请输出共有多少种使得所有皇后都无法互相直接攻击得到的方案数。
例如下面这样的摆法，是4皇后的一个解 （1代表有皇后，0代表没有）
0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
一个整数 N
能使得在 N*N 的国际象棋棋盘上放置 N 个皇后，并且所有皇后都无法互相直接攻击得到的方案数
样例输入1
4
样例输出1
2
样例输入2
8
样例输出2
92
1 \le N \le 13