Reduce to one#10272

Reduce to one

1 second

128 megabytes

Very easy

Consider a list of integers $L$ . Initially, $L$ contains all integers from $1$ to $n$ , each exactly once (later, the list may contain multiple copies of some numbers). The order of elements in $L$ does not matter. You need to perform the following operation $n - 1$ n - 1 times:

Select two elements from the list, denoted by $x$ and $y$ . They may be equal.
Remove the selected elements from $L$ .
Add the number $x + y + x \cdot y$ x + y + x \cdot y to the list.

As a result, the list will contain exactly one number. Find the maximum possible value of this number. Since the answer can be large, print it modulo $1 0^{9} + 7$ 10^9 + 7.

Input

The first line contains the number of test cases $t$ . Each of the next $t$ lines contains one integer $n (1 \leq n \leq 1 0^{6})$ n~(1 \le n \le 10^6).

Output

For each test case, print one integer — the maximum possible value of the last number in the list, computed modulo $1 0^{9} + 7$ 10^9 + 7.

Examples

Example 1

Loading

n - 1

x + y + x \cdot y

1 0^{9} + 7

n (1 \leq n \leq 1 0^{6})

1 0^{9} + 7