Consider a list of integers L. Initially L contains the integers 1 through n, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in L is not important. You should perform the following operation n−1 times:
Choose two elements of the list, let's denote them by x and y. These two elements may be equal.
Erase the chosen elements from L.
Append the number x+y+x⋅y to L.
At the end, L contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo 109+7.
The first line contains the number of test cases t. Each of the next t lines contains a single integer n (1≤n≤106).
For each test case, print a single line containing one integer — the maximum possible value of the final number in the list modulo 109+7.