Background

Xiao Y is a chubby kid. He loves going downstairs because it takes less effort, but he has obsessive-compulsive tendencies.

Because the painter HG does not have enough paint, each step is painted only halfway—either the left half or the right half—so that Xiao Y will not step on the paint when going downstairs. (Everyone: What kind of logic is this?)

Problem Description

The whole staircase has $3^N$ steps.

HG’s painting rule is: for the $I$-th step from top to bottom, if $V_3(I)$ is odd, then he paints the left half; otherwise, he paints the right half. For the definition of $V_3(I)$, see the Hint.

Because of his OCD, Xiao Y requires that he must not step on the paint.

Now he asks you for help: what is the minimum number of times he will step on the paint?

• Each move can only go down one step.
• If Xiao Y stands on the left side of the current step, then 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, then only standing on the right side counts as not stepping on the paint, and vice versa.
• The only thing Xiao Y can control is which side he stands on at step $1$. That is, Xiao Y has only $2$ possible ways to go downstairs.

Output the answer modulo $10^9+7$.

Formal Statement

Given three binary strings $A,B,C$, all of length $3^N$. String indices start 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$. For the definition of $V_3(I)$, see the Hint.

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

Find:

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

Output the answer modulo $10^9+7$.

Input Format

This problem contains multiple test cases.

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

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

Output Format

For each test case, output one line: the minimum number of times Xiao Y steps on the paint, i.e. $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$.

Output the answer modulo $10^9+7$.

1
1

1

3
494699
494699494699
494699494699494699

994161775
899186285
348815909

Hint

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

---

Test Point ID	$T \le$	$N \le$	Score
$1$	$10$		$50$
$2$	$10^5$	$10^{18}$

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

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

Translated by ChatGPT 5