311260: CF1957E. Carousel of Combinations

E. Carousel of Combinationstime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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, \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.

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$.

ExampleInput

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$.

题目大意：给定一个整数 n，函数 C(i,k) 表示从集合 {1, 2, ..., i} 中选择 k 个不同的数并以圆圈排列的不同方式的数量。需要计算表达式 ∑∑(C(i,j) mod j) 的值，其中 x mod y 表示 x 除以 y 的余数。由于这个值可能非常大，需要计算它模 10^9+7 的结果。

输入数据格式：第一行包含一个整数 t (1 ≤ t ≤ 10^5) —— 测试用例的数量。每个测试用例只有一行，包含一个整数 n (1 ≤ n ≤ 10^6)。

输出数据格式：对于每个测试用例，输出一个整数，即表达式计算结果模 10^9+7 的值。

请注意，由于这是一个翻译的概要，具体的 LaTeX 格式公式需要您根据原文中的数学表达式自行转换。题目大意：给定一个整数 n，函数 C(i,k) 表示从集合 {1, 2, ..., i} 中选择 k 个不同的数并以圆圈排列的不同方式的数量。需要计算表达式 ∑∑(C(i,j) mod j) 的值，其中 x mod y 表示 x 除以 y 的余数。由于这个值可能非常大，需要计算它模 10^9+7 的结果。 输入数据格式：第一行包含一个整数 t (1 ≤ t ≤ 10^5) —— 测试用例的数量。每个测试用例只有一行，包含一个整数 n (1 ≤ n ≤ 10^6)。 输出数据格式：对于每个测试用例，输出一个整数，即表达式计算结果模 10^9+7 的值。 请注意，由于这是一个翻译的概要，具体的 LaTeX 格式公式需要您根据原文中的数学表达式自行转换。