CF1369D.TediousLee

Lee tried so hard to make a good div.2 D problem to balance his recent contest, but it still doesn't feel good at all. Lee invented it so tediously slow that he managed to develop a phobia about div.2 D problem setting instead. And now he is hiding behind the bushes...

Let's define a Rooted Dead Bush (RDB) of level $n$ as a rooted tree constructed as described below.

A rooted dead bush of level $1$ is a single vertex. To construct an RDB of level $i$ we, at first, construct an RDB of level $i-1$, then for each vertex $u$:

• if $u$ has no children then we will add a single child to it;
• if $u$ has one child then we will add two children to it;
• if $u$ has more than one child, then we will skip it.

Rooted Dead Bushes of level $1$, $2$ and $3$.

Let's define a claw as a rooted tree with four vertices: one root vertex (called also as center) with three children. It looks like a claw:

The center of the claw is the vertex with label $1$.

Lee has a Rooted Dead Bush of level $n$. Initially, all vertices of his RDB are green.

In one move, he can choose a claw in his RDB, if all vertices in the claw are green and all vertices of the claw are children of its center, then he colors the claw's vertices in yellow.

He'd like to know the maximum number of yellow vertices he can achieve. Since the answer might be very large, print it modulo $10^9+7$.

Lee 为了平衡他最近举办的竞赛，竭尽全力设计一道优秀的 Div.2 D 题，但最终效果仍不尽如人意。Lee 设计这道题的过程过于繁琐缓慢，以至于他反而对设计 Div.2 D 题产生了恐惧心理，如今正躲在灌木丛后……

我们定义一个有根死灌木（Rooted Dead Bush, RDB），其等级为 $n$，是按如下方式构造的一棵有根树：

• 等级为 $1$ 的有根死灌木仅包含一个顶点；
• 要构造等级为 $i$ 的 RDB，我们首先构造一个等级为 $i-1$ 的 RDB；然后对其中每个顶点 $u$：
  • 若 $u$ 没有子节点，则为其添加一个子节点；
  • 若 $u$ 恰有一个子节点，则为其添加两个子节点；
  • 若 $u$ 已有两个或更多子节点，则跳过该顶点。

等级为 $1$、$2$ 和 $3$ 的有根死灌木。

我们定义一个爪形结构（claw） 为一棵含四个顶点的有根树：一个根顶点（也称作中心）拥有恰好三个子节点。其形状如下图所示：

爪形结构的中心是标号为 $1$ 的顶点。

Lee 拥有一棵等级为 $n$ 的有根死灌木。初始时，该 RDB 中所有顶点均为绿色。

在一次操作中，他可以在 RDB 中选择一个爪形结构：若该爪形结构的所有顶点均为绿色，且该爪形结构的全部三个子节点均以其中心为父节点（即它们确实是该中心的直接子节点），则他可将该爪形结构的全部四个顶点染为黄色。

他希望知道最多能将多少个顶点染成黄色。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Next $t$ lines contain test cases — one per line.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^6$) — the level of Lee's RDB.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来 $t$ 行为测试用例，每行一个。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^6$）—— 表示 Lee 的 RDB 的层数。

For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo $10^9 + 7$.

对于每个测试用例，输出一个整数——Lee 能够得到的黄色顶点的最大数量对 $10^9 + 7$ 取模的结果。

It's easy to see that the answer for RDB of level $1$ or $2$ is $0$.

The answer for RDB of level $3$ is $4$ since there is only one claw we can choose: ${1, 2, 3, 4}$.

The answer for RDB of level $4$ is $4$ since we can choose either single claw ${1, 3, 2, 4}$ or single claw ${2, 7, 5, 6}$. There are no other claws in the RDB of level $4$ (for example, we can't choose ${2, 1, 7, 6}$, since $1$ is not a child of center vertex $2$).

Rooted Dead Bush of level 4.

容易看出，层级为 $1$ 或 $2$ 的有根死灌木（RDB）的答案为 $0$。

层级为 $3$ 的 RDB 的答案为 $4$，因为其中仅存在一个可选的爪形子图：${1, 2, 3, 4}$。

层级为 $4$ 的 RDB 的答案为 $4$，因为我们可选择单个爪形子图 ${1, 3, 2, 4}$，或单个爪形子图 ${2, 7, 5, 6}$。在层级为 $4$ 的 RDB 中不存在其他爪形子图（例如，我们不能选择 ${2, 1, 7, 6}$，因为 $1$ 并非中心顶点 $2$ 的子节点）。

层级为 4 的有根死灌木（RDB）。