19366번 - Permutation and noitatumreP 다국어

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)$.