B. BIT Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Master Yi likes palindrome very much. He defines lucky strings as strings that contain exactly one palindrome substring whose length is greater than or equal to $$$2$$$.

Now, please help him find out how many lucky strings are there among all strings of length $$$n$$$ which only contains characters in $$$\{\texttt{b}, \texttt{i}, \texttt{t}\}$$$. Since this number may be too large, output it modulo $$$10^9 + 7$$$.

Input

Each test contains multiple test cases.

The first line contains an integer $$$t\ (1\le t\le 10^4$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n\ (1\le n\le 10^9)$$$.

Output

For each test case, print one integer — the number of lucky strings with length $$$n$$$ modulo $$$10^9 + 7$$$.

Example
Input
2
2
3
Output
3
18