Chef likes to spend his summer vacation playing with strings. Chef likes alternating patterns, but he only likes the characters $\texttt{a}$ and $\texttt{b}$, so he does the following:

Chef starts with an empty string S. Then,
First, he appends $\texttt{a}$ once to S
Next, he appends $\texttt{b}$ twice to S
Next, he appends $\texttt{a}$ thrice to S
Next, he appends $\texttt{b}$ four times to S

and so on. For example, the first 13 characters of S are $\texttt{abbaaabbbbaaa}$.

Now, Chef takes the string formed by the first N characters of S, and wants to calculate its beauty. The beauty of a string is calculated as follows:
First, we define the value of a string A to be the number of positions 1 ≤ i < |A| such that $A_{i} \neq A_{i+1}$. For example, the value of $\texttt{aaa}$ is 0 and the value of $\texttt{abba}$ is 2.
Then, the beauty of a string is defined to be the sum of values of all its [substrings]. Two substrings are considered distinct if they occur at different positions, so every string of length $K has exactly K\cdot(K+1)/2$ substrings.

You are given N. Help Chef by calculating the beauty of the string formed by the first N characters of S. The answer may be large, so report it modulo 1000000007.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains a single integer N.

------ Output Format ------

For each test case, output in a single line the beauty of the string modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------
3
3
4
7
----- Sample Output 1 ------
2
6
24
----- explanation 1 ------
Test case $1$: The first three characters of $S$ are $\texttt{abb}$. The values of the substrings are as follows:
- $\texttt{a}, \texttt{b}, \texttt{b}, \texttt{bb}$ have a value of $0$.
- $\texttt{ab}, \texttt{abb}$ have a value of $1$.

So, the beauty of the string is $2$.

Test case $2$: The first $4$ characters of $S$ are $\texttt{abba}$. Its substrings of non-zero value are:
- $\texttt{ab}, \texttt{abb}, \texttt{ba}, \texttt{bba}$ with value $1$
- $\texttt{abba}$ with value $2$.

So, the beauty of the string is $1 + 1 + 1 + 1 + 2 = 6$.

见题面

见题面