Given n find the value of ((nC₁)² + 2×(nC₂)² + 3×(nC₃)² + 4×(nC₄)² + ... + n×(nC_n)²) % MOD, where MOD = 10⁹+7.

Note: nCr is the number of ways of choosing r items from n items.

Input

The first line of input file contains T which denotes number of test cases. Each of the following line contains an integer n. T ≤ 1000 and n ≤ 10⁶.

Output

The output must contain T lines each line corresponding to a testcase.

Example

Input:
2
1
2
Output:
1
6