How many permutations of the first N numbers exist such that the maximum element between the indices [i..j] is either present at index i, or at index j?

Input

The first line contains the number of test cases T. Each of the next T lines contains an integer N.

Output

Output T lines containing the required answer for the corresponding test case. Since the answers can get really big, output the result modulo 1000000007.

Example

Input:
1
2
Output:
2

Constraints

1 ≤ T ≤ 10000

1 ≤ N ≤ 1000000000