Lee 非常努力地尝试做出一个好的 div.2 D 问题来平衡他最近的比赛,但感觉仍然不太好。 Lee 发明它的速度实在是太慢了,以至于他对 div.2 D 问题设置产生了恐惧症。现在他躲在灌木丛后面......
让我们将 $$$n$$$ 级别的 Rooted Dead Bush (RDB) 定义为按如下所述构造的有根树。
等级 $$$1$$$ 的有根死灌木是单个顶点。为了构造一个级别为 $$$i$$$ 的 RDB,我们首先构造一个级别为 $$$i-1$$$ 的 RDB,然后对于每个顶点 $$$u$$$:
- 如果 $$$u$$$ 没有子项,那么我们将向其添加一个子项;
- 如果 $$$u$$$ 有一个孩子,那么我们将向其添加两个孩子;
- 如果 $$$u$$$ 有多个孩子,那么我们将跳过它。
$$$1$$$、$$$2$$$ 和 $$$3$$$ 级别的生根死灌木。
让我们将爪子定义为一棵具有四个顶点的有根树:一个根顶点(也称为中心)和三个子顶点。它看起来像一只爪子:
爪子的中心是带有标签 $$$1$$$ 的顶点。
Lee 有一棵等级为 $$$n$$$ 的生根死亡灌木。最初,他的 RDB 的所有顶点都是绿色的。
在一步操作中,他可以在 RDB 中选择一个爪子,如果爪子中的所有顶点都是绿色并且爪子的所有顶点都是其中心的子节点,那么他将爪子的顶点着色为黄色。
他想知道他可以达到的黄色顶点的最大数量。由于答案可能非常大,因此打印它对 $$$10^9+7$$$ 取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行包含测试用例 - 每行一个。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^6$$$) — Lee 的 RDB 的级别。
输出
对于每个测试用例,打印一个整数 - Lee 可以对 $$$10^9 + 7$$$ 取模的黄色顶点的最大数量。
示例
输入 #1
7 1 2 3 4 5 100 2000000
输出 #1
0 0 4 4 12 990998587 804665184
注意
很容易看出$$$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 级生根枯死灌木。