题目描述

有一个N*N的矩阵方格和N个棋子，现在需要将N个棋子按要求放置到矩阵方格中。($N \leq 15$)

要求如下：

1.任意两个棋子不能在同一行

2.任意两个棋子不能在同一列

3.任意两个棋子不能在同一对角线上

根据以上要求，问N个棋子放置到N*N矩阵方格中有多少种放置方案

例如：4*4的矩阵方格，4个棋子，有2种放置方案

输入

输入一个正整数N

输出

输出放置方案数

样例

4

2

样例解释

方案1：

□ ■ □ □

□ □ □ ■

■ □ □ □

□ □ ■ □

方案2：

□ □ ■ □

■ □ □ □

□ □ □ ■

□ ■ □ □

限制

1s, 512MB 每组测试数据