环形排列之和

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

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

求

$$\sum_{i=1}^{n}\sum_{j=1}^{i}\bigl(C(i,j)\bmod j\bigr)$$

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

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

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

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

接下来 $t$ 行，每行包含一个整数 $n$。

输出格式

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

样例输入 1

4
1
3
6
314159

样例输出 1

0
4
24
78926217

数据范围

对于所有数据，$1\le t\le 10^5$，$1\le n\le 10^6$。

子任务编号	分值	特殊限制
1	20	每个测试用例均满足 $n\le 50$
2	40	每个测试用例均满足 $n\le 5000$
3		无特殊限制

提示

当 $n=1$ 时，$C(1,1)\bmod 1=0$。

当 $n=3$ 时，各项之和为 $4$。