SP22441 TILE001 - Black and White Tiles

Cradi 和 Vank 非常喜欢研究瓷砖拼接的问题。他们拥有两种宽度的矩形瓷砖：宽度为 1 厘米的瓷砖有黑色和白色两种，宽度为 2 厘米的瓷砖仅有黑色。这些瓷砖的长度可以是任意大于零的数，并且数量无限。 他们致力于创造不同的瓷砖排列方式。如果两种排列方式（无论旋转与否）的瓷砖尺寸和颜色完全吻合，则它们被认为是相同的。 他们最初选择一个边长为 1 厘米的灰色正方形瓷砖，称为 0 层排列。 在这个基础上，他们希望按照如下规则添加更多的瓷砖层： 完成 $i$ 层排列后，可以： 1. 使用 2 块长度为 $2i + 1$ 的黑色瓷砖和 2 块长度为 $2i + 3$ 的白色瓷砖（宽度均为 1 厘米），构成一个 $(i + 1)$ 层排列。 2. 使用 4 块宽度为 2 厘米、长度为 $2i + 1$ 或 $2i + 5$ 的黑色瓷砖，构成一个 $(i + 2)$ 层排列。 需要特别注意的是，在同一层内，相邻的瓷砖必须颜色不同，除非它们都是 2 厘米宽的黑色瓷砖（此时允许相邻）。下面的图片展示了一些可能的 2 层排列示例。  在探索这些排列的过程中，他们提出了一个有趣的问题：对于任意给定的层数 $n$，总共有多少种不同的 $n$ 层排列方式。请你帮助回答这个问题。由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

第一行是一个整数 $T$，代表测试用例的数量。接下来有 $T$ 行，每行包含一个整数 $n$，表示瓷砖的层数。

输出每个测试用例对应的答案，答案需对 $10^9 + 7$ 取模。

$$1 \le T \le 10^5, \quad 0 \le n \le 10^5$$ **本翻译由 AI 自动生成**