题目描述

三角形在新时代的实践中似乎极为重要，因为它代表着邪恶的三位一体（撒旦、敌基督和假先知以虚假/扭曲的信仰将人类带往新世界秩序）。三角形在光照派的所有领域中都具有首要意义，无论是在玫瑰十字会和共济会的仪式上，还是在其他光照派追随者的巫术、占星和黑魔法实践中。

有一天，你发现了一类神秘的图案。这些图案可以分为不同的度数。一个度数为 $n$ 的图案由 $\frac{n(n+1)}{2}$ 个边长为 $1$ 的小正三角形组成，所有小三角形方向相同，拼成一个大三角形。下图展示了度数为 $3$ 的图案，所有小正三角形均被高亮显示。

:::align{center} :::

由于该图案包含许多正三角形，极其邪恶且不可接受，你希望计算由图案中的顶点构成的正三角形的数量，以便估计光照派的实力。这里的正三角形不要求每条边都与大三角形的某条边平行。下图展示了度数为 $3$ 的图案中由顶点构成的两个正三角形。

:::align{center} :::

由于答案可能非常巨大，你只需要计算其模 $10^9+7$ 的结果。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^6$）——测试数据的组数。

接下来的 $t$ 行，每行包含一个整数 $n$（$1 \le n \le 10^9$）——图案的度数。

输出格式

对于每组测试数据，在一行中输出一个整数——正三角形的数量模 $10^9+7$ 的结果。

3
1
2
3

1
5
15

提示

翻译由 DeepSeek V4 Pro 完成