E. 循环排列组合数

每次测试的时间限制：2.5 秒
每次测试的内存限制：256 兆字节

题目描述

给定一个整数 $n$。函数 $C(i, k)$ 表示从集合 $\{1, 2, \dots, i\}$ 中选出 $k$ 个不同的数，并将它们排成一个圆环† 的不同方式的数量。

请计算
$ \sum_{i=1}^{n} \sum_{j=1}^{i} \left( C(i, j) \bmod j \right). $
这里 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

由于这个结果可能非常大，请输出它对 $10^9 + 7$ 取模的值。

† 在圆环排列中，如果两个序列可以通过旋转相互得到，则认为它们是相同的。例如，$[1,2,3]$ 和 $[2,3,1]$ 在圆环意义下是等价的。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^5$）——测试用例的数量。

每个测试用例只有一行，包含一个整数 $n$（$1 \le n \le 10^6$）。

输出格式

对于每个测试用例，输出一行一个整数，表示所求表达式对 $10^9 + 7$ 取模后的结果。

示例

输入

4
1
3
6
314159

输出

0
4
24
78926217

说明

在第一个测试用例中，$C(1,1) \bmod 1 = 0$。

在第二个测试用例中：

• $C(1,1) = 1$（排列为：$[1]$）；
• $C(2,1) = 2$（排列为：$[1]$，$[2]$）；
• $C(2,2) = 1$（排列为：$[1,2]$）；
• $C(3,1) = 3$（排列为：$[1]$，$[2]$，$[3]$）；
• $C(3,2) = 3$（排列为：$[1,2]$，$[2,3]$，$[3,1]$）；
• $C(3,3) = 2$（排列为：$[1,2,3]$，$[1,3,2]$）。

总和为
$ (C(1,1) \bmod 1) + (C(2,1) \bmod 1) + (C(2,2) \bmod 2) + (C(3,1) \bmod 1) + (C(3,2) \bmod 2) + (C(3,3) \bmod 3) = 4. $