시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Bobo would like to count the number of permutations $(p_1, p_2, \dots, p_n)$ of $\{1, 2, \dots, n\}$ such that the sequence $q = (p_1, p_2, \dots, p_n, p_n, p_{n - 1}, \dots, p_1)$ does not contain four indices $1 \leq a < b < c < d \leq 2n$ which satisfy $q(a) < q(c) < q(d) < q(b)$.

As this number may be very large, Bobo is only interested in its remainder modulo $(10^9+7)$.

입력

The input contains zero or more test cases, and is terminated by end-of-file.

Each test case contains an integer $n$ ($1 \leq n \leq 10^9$). 

It is guaranteed that the number of test cases does not exceed $2 \cdot 10^4$.

출력

For each test case, output an integer which denotes the number of ways modulo $(10^9+7)$.

예제 입력 1

4
1000000000

예제 출력 1

16
861159011