Description

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

Input Format

一个整数N

Output Format

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

4

8

2

92​
``

Hint

1<=N<=13