Time Limit: 1000ms

Description

Given N distinct elements, how many permutations we can get from all the possible subset of the elements?

Input

The first line is an integer T that stands for the number of test cases. Then T line follow and each line is a test case consisted of an integer N. Constraints: T is in the range of [0, 10000] N is in the range of [0, 8000000]

Output

For each case output the answer modulo 1000000007 in a single line.

Sample Input

5 0 1 2 3 4

Sample Output

0 1 4 15 64

Author

baihacker