NOVICE62 - Match the words

You may have come across questions like, Match-The-Following 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 match-the-following 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 vice-versa.

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

Added by:amit karmakar
Date:2011-07-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem......

hide comments
2020-12-01 11:54:55
If getting TLE, just preprocess for all n=1000000 in an array. Then just return the value at arr[n]. Derangements is the concept here.
2015-12-11 14:58:47
For N = 1,000,000 answer = 102,701,088
2013-07-24 12:22:54 aman kumar jha
@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: 2013-07-24 12:23:28
2013-06-19 09:58:26 vikash singh
derangements
2013-05-23 18:01:02 Udyan Khurana
can somebody tell me the answer of n=13 to 17?
2012-06-07 18:34:31 Nikhar Agrawal
use long long int in c++...gave WA with long int.. but got accepted with long long.
2012-01-10 08:25:24 Devil D
I got the logic but its getting TLE ...:(
2011-12-06 09:27:49 Ankit Paharia
how the output is 1854 for 7.......
for 7--> all possible solutions - (atleast 1 solution is correct )... plzz help me out....
2011-10-03 09:28:53 Niteesh
nice logical problem indeed.
2011-09-27 19:52:27 :D
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 :)

FIXED thanks :)

Last edit: 2011-09-27 19:52:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.