题目描述

给定一个大小为 $n \times n$ 的国际象棋棋盘，现在要在这个棋盘上放置 恰好 $n$ 个车（Rook），使得任意两个车都不在同一行且不在同一列（即它们互不攻击）。
请计算一共有多少种不同的放置方案。

注意：棋盘上的格子均无障碍，所有格子均可放置车。两个方案不同当且仅当存在至少一个格子在一个方案中有车而在另一个方案中没有车。

输入格式

输入只有一行，包含一个整数 $n$。

输出格式

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

样例输入 1

3

样例输出 1

6

样例输入 2

4

样例输出 2

24

评测数据规模

$1 \le n \le 8$