题目背景

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

对于 $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$。