说明

时间限制：1 Sec 内存限制：256 MB 输入文件：seq.in 输出文件：seq.out

请计算由下述递推式定义的数列 $\{a\}$ 的第 $n$ 项对 $10^9+7$ 取模的结果。

递推式如下：

$a_1=1$

当 $n \neq 1$ 时：

- 若 $n$ 为偶数，则 $a_n = n \times (a_1 + a_3 + a_5 + \dots + a_{n-1})$

- 若 $n$ 为奇数，则 $a_n = n \times (a_2 + a_4 + a_6 + \dots + a_{n-1})$

输入格式

一个整数 $n$。

输出格式

输出数列 $\{a\}$ 的第 $n$ 项对 $10^9+7$ 取模的结果。

样例

样例 1

2

2

样例说明：

$a_2 = 2 \times a_1 = 2$

样例 2

4

28

样例说明：

$a_4 = 4 \times (a_1 + a_3) = 28$

样例 3

6

942

样例说明：

$a_6 = 6 \times (a_1 + a_3 + a_5) = 942$

数据范围

对于 30% 的数据，$n \le 5000$。

对于 100% 的数据，$1 \le n \le 10^5$。