I. Permutation Prefix Max
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$p_1, p_2, \dots, p_n$$$ be a permutation of the integers $$$\{1, 2, \dots, n\}$$$.

Define the prefix maximum array $$$b_1, b_2, \dots, b_n$$$ for the permutation $$$p$$$ as follows: $$$$$$ b_i = \max(p_1, p_2, \dots, p_i) \quad \text{for } (1 \le i \le n) $$$$$$

The permutation $$$p$$$ is called good if its prefix maximum array $$$b$$$ satisfies the following condition: $$$$$$ b_i - b_{i-1} \le 1 \quad \text{for all } i \text{ such that } (2 \le i \le n) $$$$$$

Given an integer $$$n$$$, your task is to count the number of good permutations of size $$$n$$$. Since the count can be large, output the result modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), the number of test cases.

Then $$$T$$$ test cases follow.

Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer representing the number of good permutations of size $$$n$$$, modulo $$$10^9 + 7$$$.

Example
Input
5
1
2
3
4
5
Output
1
2
5
16
65