题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入格式

第一行一个正整数 $n$，表示棋盘的行列。以及皇后数量。

输出格式

仅一个整数，表示有几种方法。

样例 #1

样例输入 #1

4

样例输出 #1

2

提示

• 对于 $30\%$ 的数据，$1\le n,m\le 5\times10^3$，$1\le K\le 500$；
• 对于另外 $10\%$ 的数据，$K=1$；
• 对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^4$，$1\le K\le 500$。