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,…,i} and arrange them in a circle†.
Find the value of n∑i=1i∑j=1(C(i,j)mod 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 |
---|