NOVICE62 - Match the words

no tags 

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

hide comments
hodobox: 2015-12-11 14:58:47

For N = 1,000,000 answer = 102,701,088

aman kumar jha: 2013-07-24 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: 2013-07-24 12:23:28
vikash singh: 2013-06-19 09:58:26

derangements

Udyan Khurana: 2013-05-23 18:01:02

can somebody tell me the answer of n=13 to 17?

Nikhar Agrawal: 2012-06-07 18:34:31

use long long int in c++...gave WA with long int.. but got accepted with long long.

Devil D: 2012-01-10 08:25:24

I got the logic but its getting TLE ...:(

Ankit Paharia: 2011-12-06 09:27:49

how the output is 1854 for 7.......
for 7--> all possible solutions - (atleast 1 solution is correct )... plzz help me out....

Niteesh: 2011-10-03 09:28:53

nice logical problem indeed.

:D: 2011-09-27 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 :)

FIXED thanks :)

Last edit: 2011-09-27 19:52:55
Robin Lee: 2011-09-27 19:52:27

Very nice indeed.


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......