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

Input

The first line contains 1 ≤ T ≤ 105 , number of test-cases.

Each of following T lines contains 1 ≤ N ≤ 107, 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
hacking_bot: 2018-09-08 15:10:32

Ez derangements question

mag1x_: 2018-05-29 13:58:10

calculated for first 5 numbers and looked for a pattern & bingo AC :D

holmesherlock: 2017-10-29 07:59:45

I tried precomputation using derangement formula but it gave me tle..:-(


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