← 返回题目列表

Codeforces · 1957/E

E. 组合轮播

中文机器翻译题面 查看原题

给你一个整数$$$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]$$$)。