题目背景

Y 同学学校的食堂实在是太挤了！于是，他决定邀请他的一些好友去校外聚餐，并在一家酒店包下了一张大圆桌。当同学们都到齐后，Y 同学惊讶地发现，到场的恰好是 $N$ 对情侣。为了保护在场的单身狗（比如他自己）的弱小心灵，他决定制定一个特殊的座位安排规则。

题目描述

有 $N$ 对情侣（共 $2N$ 个人）需要入座。酒店的桌子是一张恰好有 $2N$ 个位置的圆桌，所有人都会入座，没有空位。

为了避免“秀恩爱”的场面，Y 同学规定，任意一对情侣的座位都不能相邻。

你需要计算，满足这个条件的情况下，总共有多少种不同的就座方案。

请注意：

• 桌子的每一个位置都是相同的。如果两种方案可以通过旋转互相得到，那么它们被视为同一种方案。
• 所有情侣都是可区分的，每个人也是可区分的。

由于答案可能非常大，请将结果对 $10^9 + 7$ 取模。

输入格式

输入一行，包含一个正整数 $N$，表示情侣的对数。

输出格式

输出一行，一个非负整数，表示满足条件的方案数对 $10^9 + 7$ 取模后的值。

样例

样例输入 #1

2

样例输出 #1

2

样例输入 #2

25

样例输出 #2

535659175

提示

样例 1 解释

假设两对情侣分别是 (A, a) 和 (B, b)。 为了处理旋转同构，我们先固定 A 的位置。那么剩下的 3 个位置需要安排 a, B, b。

• a 不能坐在 A 的左边或右边。所以 a 必须坐在 A 的对面。
• 剩下的两个位置留给 B 和 b。他们可以互换位置。
• 方案一：A, B, a, b
• 方案二：A, b, a, B
• 总共有 2 种合法的方案。

数据范围与约定

对于 $100\%$ 的数据，$1 \le N \le 3 \times 10^7$。