在“新纪元”修行中，三角形的使用似乎非常重要，因为它代表了邪恶的三位一体（撒旦、敌基督和假先知，通过虚假/扭曲的信仰将人类带入新世界秩序）。三角形在所有光照派领域中都具有首要地位，无论是在玫瑰十字会和共济会的仪式中，还是在其他光照派追随者的巫术、占星术和黑魔法实践中。

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

由于该图案包含许多正三角形，这非常邪恶且不可接受，因此你想计算由图案中的顶点所构成的正三角形的数量，以便估算光照派的力量。正三角形的边不一定需要与大三角形的某条边平行。下图展示了在 3 度图案中由顶点构成的两个正三角形。

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

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^6$)，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$ ($1 \le n \le 10^9$)，表示图案的度数。

输出格式

对于每个测试用例，输出一行一个整数，表示正三角形的数量对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3
1
2
3

样例输出 1

1
5
15