# 「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
1
```

### 样例输出 #1

```
1
```

## 样例 #2

### 样例输入 #2

```
3
494699
494699494699
494699494699494699
```

### 样例输出 #2

```
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$。