NOVICE62  Match the words
You may have come across questions like, MatchTheFollowing words with their synonyms in the second column and alike. Ted also stumbled upon one such question. Being weak at english, he tried guessing the answers. While he guessed, he thought about how unlucky he was at guessing.
Being also weak at math, he needs help from you for a slightly different task. Find the total number of ways of completing the solution to this question in which he gets none of the matches correct.
Note: In the matchthefollowing problem, there are two columns of words. Each column contains N words. Words in the first column have to be matched with words in the second column. A valid solution to this question requires every word in the first column to be matched with only one word in the second column and viceversa.
Input
First line contains a single integer T(1 <= T <= 1000) denoting the total number of test cases. Each test case contains a single integer N (1 <= N <= 1000000).
Output
For each test case, print a single integer the required number of ways modulo 1000000007
Example
Input: 3 1 2 7
Output: 0 1 1854
hide comments
hodobox:
20151211 14:58:47
For N = 1,000,000 answer = 102,701,088 

aman kumar jha:
20130724 12:22:54
@Ankit Paharia let N=7, according to question u have to find the "maximum number of ways in which ted gets "none" of the matches correct". it means if 1st match is right , then no matter that others 6 matches are correct or not, it will not be counted. Last edit: 20130724 12:23:28 

vikash singh:
20130619 09:58:26
derangements 

Udyan Khurana:
20130523 18:01:02
can somebody tell me the answer of n=13 to 17? 

Nikhar Agrawal:
20120607 18:34:31
use long long int in c++...gave WA with long int.. but got accepted with long long. 

Devil D:
20120110 08:25:24
I got the logic but its getting TLE ...:( 

Ankit Paharia:
20111206 09:27:49
how the output is 1854 for 7.......


Niteesh:
20111003 09:28:53
nice logical problem indeed. 

:D:
20110927 19:52:27
Nice problem. There's an error in the input specification. It should probably be "(1 <= N <= 1000000)". As it is now it's a little bit redundant :)


Robin Lee:
20110927 19:52:27
Very nice indeed. 
Added by:  amit karmakar 
Date:  20110702 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem...... 