You are given an integer $$$n$$$. The function $$$C(i,k)$$$ represents the number of distinct ways you can select $$$k$$$ distinct numbers from the set {$$$1, 2, \ldots, i$$$} and arrange them in a circle$$$^\dagger$$$.
Find the value of $$$$$$ \sum\limits_{i=1}^n \sum\limits_{j=1}^i \left( C(i,j) \bmod j \right). $$$$$$ Here, the operation $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.
Since this value can be very large, find it modulo $$$10^9+7$$$.
$$$^\dagger$$$ In a circular arrangement, sequences are considered identical if one can be rotated to match the other. For instance, $$$[1, 2, 3]$$$ and $$$[2, 3, 1]$$$ are equivalent in a circle.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.
The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).
For each test case, output a single integer on a new line — the value of the expression to be calculated modulo $$$10^9+7$$$.
4136314159
0 4 24 78926217
In the first test case, $$$C(1,1) \bmod 1 = 0$$$.
In the second test case:
Name |
---|