Given N distinct characters, How many distinct n letter words can be formed.

Constraints :
For 60 Points : 
1 ≤ T  ≤ 10³
1 ≤ N ≤ 10³

For 40 Points : 
1 ≤ T  ≤ 10⁵
1 ≤ N ≤ 10⁵

Input :

First Line contains T number of test case.
Each of the next T lines contain an Integer N.

Output :

For each test case print number of distinct n letter words mod 10⁹+7 in a new line.