题目描述

我们有一个大小为 $n \times n$ 的国际象棋棋盘，所有格子均无障碍。现在要在这个棋盘上放置 恰好 $n$ 个骑士，使得任意两个骑士都不在同一条对角线上（包括主对角线和副对角线方向），即它们不能互相攻击。

注意：这里的“骑士”移动方式被定义为沿斜线（对角线方向）移动，而不是国际象棋中标准的日字形走法。也就是说，两个骑士如果位于同一条主对角线（$r-c$ 为定值）或同一条副对角线（$r+c$ 为定值）上，则它们互相攻击。

请你计算一共有多少种不同的放置方案。

两个方案不同当且仅当存在至少一个格子在一种方案中有骑士而在另一种方案中没有。

输入格式

输入只有一行，包含一个整数 $n$。$(1\le n\le 6)$

输出格式

输出一个整数，表示满足条件的放置方案总数。

样例输入 1

1

样例输出 1

1

样例输入 2

2

样例输出 2

4

样例输入 3

3

样例输出 3

8

。