题目背景

小H 今天迷上了几何……

题目描述

自从 小H 了解了 Catalan数 之后，他萌生了一个奇妙的想法：

• 既然知道了一个圆，其上有 $n$ 个点，那么这些点之间用可以相交的弦分割成若干个区域，设 $m$ 为能分割的区域数量，那 $m$ 的最大值是多少呢？

跟往常一样，小H 想让你帮他解决这道题。

输入格式

本题有多个测试数据 $T$。

第一行一个整数 $T$；

接下来 $T$ 行，每行一个整数 $n$，表示圆上有 $n$ 个点。

输出格式

输出共 $T$ 行，每行输出 $\max(m)$ 的值；

PS: 由于答案可能很大，小H 只需要你告诉他最终结果 $\mod 10^9 + 7$ 后的值。

输入输出样例

3
2
6
10

2
31
256

说明/提示

可以参考欧拉示性数公式。

对于 $20\%$ 的数据，$1 \leq T \leq 50$，$1 \leq n \leq 300$

对于 $60\%$ 的数据，$1 \leq T \leq 3000$，$1 \leq n \leq 10^3$

对于 $100\%$ 的数据，$1 \leq T \leq 700000$，$1 \leq n \leq 10^7$