题目描述

在一张的国际象棋棋盘上，放置个皇后，使得所有皇后都无法互相直接攻击得到，（皇后可以直接攻击到她所在的横行，竖列，斜方向上的棋子），现在输入一个整数，表示在的棋盘上放个皇后，请输出共有多少种使得所有皇后都无法互相直接攻击得到的方案数。 例如下面这样的摆法，是 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

数据范围与提示

1<=N<=13