Bobo 想要计算 $\{1, 2, \dots, n\}$ 的排列 $(p_1, p_2, \dots, p_n)$ 的数量，使得序列 $q = (p_1, p_2, \dots, p_n, p_n, p_{n-1}, \dots, p_1)$ 不包含满足 $q(a) < q(c) < q(d) < q(b)$ 的四个下标 $1 \le a < b < c < d \le 2n$。
由于这个数字可能非常大，Bobo 只对它除以 $(10^9 + 7)$ 的余数感兴趣。
输入格式
输入包含零个或多个测试用例，并以文件结束符（end-of-file）终止。 每个测试用例包含一个整数 $n$ ($1 \le n \le 10^9$)。 保证测试用例的数量不超过 $2 \cdot 10^4$。
输出格式
对于每个测试用例，输出一个整数，表示满足条件的排列数量对 $(10^9 + 7)$ 取模的结果。
样例
样例输入 1
4 1000000000
样例输出 1
16 861159011