410476: GYM104025 B BIT Palindrome

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

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

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

2
2
3

3
18