「FAOI-R2」Paint (A)

小 Y 是一个胖子，他最爱下楼梯了，因为下楼梯很省力气，但是他却有强迫症。 由于刷漆工人 HG 的油漆不够，每一层台阶都只刷了一半——左边或右边，好让小 Y 下楼时不踩到油漆。（~~众人：这是什么逻辑？~~）

整个楼梯共 $3^N$ 级台阶。 HG 刷漆的规律是：对于**从上到下**第 $I$ 级台阶，若 $V_3(I)$ 是奇数，则刷在左边，否则刷在右边。**$V_3(I)$ 的定义请见提示。** 小 Y 因为强迫症，要求自己不能踩到油漆。 现在他来求助你，他最少会踩到油漆多少次？ - 一次只能下一级台阶。 - 如果小 Y 站在当前台阶的左边，则他必须站在下一级台阶的右边，反之亦然。 - 如果油漆在当前台阶左边，那么需要站在当前台阶右边才算没踩到油漆，反之亦然。 - 小 Y 唯一可以控制的是：他在第 $1$ 级台阶上站在哪边。也就是说，小 Y 只有 $2$ 种下楼梯的方案供选择。 答案对 $10^9+7$ 取模。 ### 形式化题意 给定三个 01 串 $A,B,C$，长度均为 $3^N$。字符串下标从 $1$ 开始。 其中： - $A=\texttt{101010101\ldots101}$； - $B=\texttt{010101010\ldots010}$； - $C=\texttt{001001000\ldots}$；具体来说，第 $I$ 个字符为 $V_3(I) \bmod 2$。**$V_3(I)$ 的定义请见提示。** 记 $\operatorname{mc}(X,Y)$ 为字符串 $X$ 和 $Y$ 中匹配的字符的个数。 试求： $$\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$$ 答案对 $10^9+7$ 取模。

**本题有多组数据。** 第一行，一个正整数 $T$，代表数据组数。 下面 $T$ 行，每行一个正整数 $N$。

每组数据一行，输出踩到油漆的最少次数，即 $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$。 **答案对 $10^9+7$ 取模。**

1
1

1

3
494699
494699494699
494699494699494699

994161775
899186285
348815909

样例 $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$。 ------------ | 测试点编号 | $T \le$ | $N \le$ | 分值 | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $50$ | | $2$ | $10^5$ | $10^{18}$ | $50$ | 对于 $100\%$ 的数据，$1 \le T \le 10^{5}$，$1 \le N \le 10^{18}$。 > **提示：** $V_3(X)$ 指 $X$ 中质因数 $3$ 的个数。例如，$V_3(14)=0$，$V_3(18)=2$。