题目描述

在一张$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$