题目描述

给出一个 $n\times n$ 的国际象棋棋盘，你需要在棋盘中摆放 $n$ 个皇后，使得任意两个皇后之间不能互相攻击。具体来说，不能存在两个皇后位于同一行、同一列，或者同一对角线。请问共有多少种摆放方式满足条件。

输入格式

一行，一个整数 $n\ (1\le n \le 12)$，表示棋盘的大小。

输出格式

输出一行一个整数，表示总共有多少种摆放皇后的方案，使得它们两两不能互相攻击。

输入样例

4

输出样例

2