As we all know Aakash has many girlfriends, he wants make sure that he does not take his girl to the same restaurant twice. Since there are only N restaurants in the city and hence he chose not to have more than N girlfriends! Hence currently he has N girlfriends.
He has already taken all his girl once on date, where no two girls went to the same restaurant.
Now he plans to take them all on a date once again. Tell him how many ways are possible to plan the trip such that no girl is taken to the same restaurant where she has already been before and also no two of them goes to the same restaurant.
Input:
First line of the input contains T test cases, and for each test case we have N (girlfriends and restaurants)).
Output:
Output the value modulo 1000000007
Contraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10000000
Sample Input
2
2
3
Sample Output
1
2