Given n find the value of ((nC₁)²+2*(nC₂)²+3*(nC₃)²+4*(nC₄)²+ ... +n*(nC_n)²)% MOD, where MOD=10^9+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^6.

Output

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

Example

Input:
2
1
2
Output:
1
6