给你一个整数$$$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$$$ 为模计算的表达式的值。
示例
输入 #1
4 1 3 6 314159
输出 #1
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]$$$)。