Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Carousel of Combinations
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ni=1ij=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.

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.

Example
Input
4
1
3
6
314159
Output
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]).
In total, \left(C(1,1) \bmod 1\right) + \left(C(2,1) \bmod 1\right) + \left(C(2,2) \bmod 2\right) + \left(C(3,1) \bmod 1\right) + \left(C(3,2) \bmod 2\right) + \left(C(3,3) \bmod 3\right) = 4.