Byteman 在下午 5 点整敲响了 Byteguy 的门。其实这完全没必要，因为 Byteguy 很了解他的准时，正准备去开门。

喝过一杯热茶后，Byteguy 拿出一副棋盘准备下棋，正如他们计划的那样。但 Byteman 说，完全信息博弈不够有挑战性，做点别的或许是个好主意。由于想不出充分的理由反驳，Byteguy 只好同意了。他们花了一些时间寻找从未尝试过的智力挑战，过了一会儿，朋友们决定解决以下问题。

给定一个 $n \times n$ 的棋盘。计算有多少种放置 $n$ 个车的方法，使得每一列和每一行中最多只有一个车。此外，棋盘在旋转 90°（在水平面上）后，车的排列方式必须与旋转前完全相同。

棋盘格子的颜色在旋转后可能会改变，但这在这里并不重要。

输入格式

标准输入的第一行也是唯一一行包含一个整数 $n$ ($1 \le n \le 50\,000$)。

输出格式

程序应向标准输出写入一行，包含一个整数，即在 $n \times n$ 棋盘上放置 $n$ 个车的所有不同排列方案数，要求每行每列最多只有一个车，且该排列在旋转 90° 后保持不变。

样例

输入 1

1

输出 1

1