### 问题描述 小然在他的夏日假期里，喜欢用字符串进行游戏。他特别喜欢交替出现的模式，但他只喜欢字符 'a' 和 'b'，所以他开始了如下的游戏： 小然首先创建一个空字符串 $S$，然后： 1. 首先，他在 $S$ 的末尾添加一个 'a'。 2. 然后，他在 $S$ 的末尾添加两个 'b'。 3. 接下来，他在 $S$ 的末尾添加三个 'a'。 4. 然后，他在 $S$ 的末尾添加四个 'b'。 5. 以此类推。例如，$S$ 的前 13 个字符是 "abbaaabbbbaaa"。 现在，小然取出 $S$ 的前 $N$ 个字符，然后计算它的美丽度。字符串的美丽度定义如下： 1. 首先，我们定义一个字符串 $A$ 的值是满足 $A_i \neq A_{i+1}$ 的位置 $i$（$1 \leq i < |A|$）的数量。例如，字符串 "aaa" 的值是 0，字符串 "abba" 的值是 2。 2. 然后，字符串的美丽度定义为所有子字符串的值的和。两个子字符串如果在不同的位置则被认为是不同的，因此长度为 $K$ 的字符串有恰好 $\dfrac{K \cdot (K + 1) }{2}$ 个子字符串。 你的任务是，给定 $N$，计算由 $S$ 的前 $N$ 个字符组成的字符串的美丽度。由于答案可能非常大，所以请你将答案对 $10^9 + 7$ 取模后输出。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含一行，包含一个整数 $N$。 ### 输出格式 对于每个测试用例，输出一行，包含一个整数，表示字符串的美丽度对 $10^9 + 7$ 取模后的结果。 ### 样例输入 ``` 3 3 4 7 ``` ### 样例输出 ``` 2 6 24 ``` ### 说明 在第一个测试用例中，$S$ 的前两个字符是 "ab"。其子字符串的值如下： - "a"、"b" 的值为 $0$。 - "ab" 的值为 $1$。 所以，字符串的美丽度为 $2$。 在第二个测试用例中，$S$ 的前四个字符是 "abba"。其子字符串的值如下： - "a"、"b"、"bb" 的值为 $0$。 - "ab"、"abb"、"ba"、"bba" 的值为 $1$。 - "abba" 的值为 $2$。 所以，字符串的美丽度为 $6$。 ### 评测数据范围 $1 \leq T \leq 10^5$。 $1 \leq N \leq 10^9$。