Carousel of Combinations
Description
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$.
Input
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$).
Output
For each test case, output a single integer on a new line — the value of the expression to be calculated modulo $10^9+7$.
4
1
3
6
314159
0
4
24
78926217
Note
In the first test case, $C(1,1) \bmod 1 = 0$.
In the second test case:
- $C(1,1)=1$ (the arrangements are: $[1]$);
- $C(2,1)=2$ (the arrangements are: $[1]$, $[2]$);
- $C(2,2)=1$ (the arrangements are: $[1, 2]$);
- $C(3,1)=3$ (the arrangements are: $[1]$, $[2]$, $[3]$);
- $C(3,2)=3$ (the arrangements are: $[1, 2]$, $[2, 3]$, $[3, 1]$);
- $C(3,3)=2$ (the arrangements are: $[1, 2, 3]$, $[1, 3, 2]$).