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

Input

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

Each of following T lines contains 1 ≤ N ≤ 10⁷, 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