YAPP - Yet Another Permutations Problem

How many permutations of the first N numbers exist such that the maximum element between the indices [i..j] is either present at index i, or at index j ?


Input

The first line contains the number of test cases T. Each of the next T lines contains an integer N


Output

Output T lines containing the required answer for the corresponding test case. Since the answers can get really big, output the result modulo 1000000007.

Example

Sample Input:
1
2

Sample Output:
2

Constraints

1 <= T <= 10000

1 <= N <= 1000000000


Added by:Varun Jalan
Date:2010-01-25
Time limit:1.690s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem used for Technovanza

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.