ADADUNG  Ada and Manure
As you might know Ada the Ladybug is farmer. Last year, she sowed N distinct types of grain to N distinct places. This year she wants to seed the same types of grain again, yet there is a little problem: each type of grain needs special kind of manure, yet fertilizing soil with same kind of manure in consecutive years might destroy it.
Now she is asking you to count the number of ways, to seed N types of grain to N places in such way that no type of grain will be in its original place. Since this number might be pretty big, print it modulo 10^{9}+7.
Input
The first line contains 1 ≤ T ≤ 10^{5} , number of testcases.
Each of following T lines contains 1 ≤ N ≤ 10^{7}, number of types/places.
Output
For each test case, print the number of possibilities for given number of types/places modulo 1000000007.
Example Input
5 2 3 10 100 666
Example Output
1 2 1334961 944828409 769756093
hide comments
tarun_28:
20200921 10:44:14
Bruteforce for pattern;) 

aditya_rev:
20200512 09:56:49
How do people optimize precompute so they reach running time under 0.5? 

bmad_221:
20191217 11:38:55
just go with @mag1x_


Asokan R:
20191024 20:21:49
java > TLE, same in cpp accepted 

hacking_bot:
20180908 15:10:32
Ez derangements question 

mag1x_:
20180529 13:58:10
calculated for first 5 numbers and looked for a pattern & bingo AC :D


holmesherlock:
20171029 07:59:45
I tried precomputation using derangement formula but it gave me tle..:(

Added by:  Morass 
Date:  20170211 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 