Problem Background

Xiao Y is a bit overweight and loves descending stairs because it saves energy, but he has obsessive-compulsive disorder.

Due to the lack of paint from the painter HG, each step is only painted on one side—either the left or the right—to ensure that Xiao Y doesn't step on the paint while descending. (Everyone: What kind of logic is that?)

Problem Description

The entire staircase consists of $3^N$ steps.

HG's painting pattern is as follows: For the top-to-bottom $I$-th step, if $V_3(I)$ is odd, it is painted on the left; otherwise, it is painted on the right. See the hints for the definition of $V_3(I)$.

Xiao Y, due to his obsessive-compulsive disorder, requires that he must not step on any paint.

• He can only descend one step at a time.
• If Xiao Y is standing on the left side of the current step, he must stand on the right side of the next step, and vice versa.
• If the paint is on the left side of the current step, he must stand on the right side to avoid stepping on the paint, and vice versa.
• The only control Xiao Y has is which side he starts on the first step. That is, Xiao Y has only 2 options for descending the stairs.

Find the minimum number of times he will step on the paint, modulo $10^9+7$.

Formal Problem Statement

Given three 01 strings $A, B, C$, each of length $3^N$. The strings are indexed from 1.

Where:

• $A = \texttt{101010101\ldots101}$;
• $B = \texttt{010101010\ldots010}$;
• $C = \texttt{001001000\ldots}$; specifically, the $I$-th character is $V_3(I) \bmod 2$. See the hints for the definition of $V_3(I)$.

Let $\operatorname{mc}(X, Y)$ denote the number of matching characters between strings $X$ and $Y$.

Find:

$$\min\{\operatorname{mc}(A, C), \operatorname{mc}(B, C)\}$$

The answer should be taken modulo $10^9+7$.

Input and Output Format

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

The next $T$ lines each contain a positive integer $N$.

Output Format

For each test case, output a line containing the minimum number of times Xiao Y will step on the paint, i.e., $\min\{\operatorname{mc}(A, C), \operatorname{mc}(B, C)\}$, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

1
1

Sample Output #1

1

Sample Input #2

3
494699
494699494699
494699494699494699

Sample Output #2

994161775
899186285
348815909

Notes

For sample #1:

• $A = \texttt{101}$;
• $B = \texttt{010}$;
• $C = \texttt{001}$;
• $\operatorname{mc}(A, C) = 2$;
• $\operatorname{mc}(B, C) = 1$;
• $\min\{\operatorname{mc}(A, C), \operatorname{mc}(B, C)\} = 1$.

For $100\%$ of the data, $1 \le T \le 10^5$, $1 \le N \le 10^{18}$.

Hint: $V_3(X)$ refers to the number of prime factors of 3 in $X$. For example, $V_3(14) = 0$, $V_3(18) = 2$.

见题面 Input 部分

见题面 Output 部分