N皇后问题

题目描述

在 $N\times N$ 的方格棋盘放置了 $N$ 个皇后，使得它们不相互攻击（即任意 $2$ 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 $45$ 角的斜线上。你的任务是，对于给定的 $N$，求出有多少种合法的放置方法。

输入描述

输入中有一个正整数 $N≤10$，表示棋盘和皇后的数量

输出描述

为一个正整数，表示对应输入行的皇后的不同放置数量。

输入输出样例

示例 1

>输入

5

>输出

10