CF1957E.Carousel of Combinations

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

求下式的值：

$$\sum\limits_{i=1}^n \sum\limits_{j=1}^i \left( C(i,j) \bmod j \right)$$

这里，$x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

$^\dagger$ 在环形排列中，如果一个序列可以通过旋转变成另一个序列，则认为它们是相同的。例如，$[1,2,3]$ 和 $[2,3,1]$ 在环中是等价的。

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

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

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

在第一个测试用例中，$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]）。

因此，总和为 $\left(C(1,1) \bmod 1\right) + \left(C(2,1) \bmod 1\right) + \left(C(2,2) \bmod 2\right) + \left(C(3,1) \bmod 1\right) + \left(C(3,2) \bmod 2\right) + \left(C(3,3) \bmod 3\right) = 4$。

由 ChatGPT 4.1 翻译