P10035 "FAOI-R2" Paint

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?~~)

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

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

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

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$ | $10$ | $50$ | | $2$ | $10^5$ | $10^{18}$ | $50$ | 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