题目背景

翻译自 CSES-2413 题。

题目描述

你的任务是构建一个宽度为 $2$，高度为 $n$ 的塔。你有无限供应的块，这些块的宽度和高度都是整数。

例如，给定 $n=6$ 时，以下是一些可能的解决方案：

对于给定的 $n$，你需要计算可以构建多少种不同的塔。旋转和镜像不同的塔要分别计数。

输入格式

第一行包含一个整数 $t$，代表测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$，代表塔的高度。

输出格式

对于每个测试用例，输出一个整数，表示可以构建的塔的数量，结果对 $10^9+7$ 取模。

样例

3
2
6
1337

8
2864
640403945

说明/提示

$1\le n \le 10^6$；

$1 \leq t \leq 100$。