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
hide comments
appy:
20140529 16:53:55
More test cases pls


Anubhav Balodhi :
20140314 09:51:15
Doing too much PnC makes this problem very simple ;D 

god_father:
20121222 13:50:41
very easy move it to tutorial...& n=5 ans is 16. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120616 19:39:06
optimize I/O, use precomputation, then AC 0.02s :)


Aniket Divekar:
20111218 06:17:28
@Varun : what are i and j exactly....they are not in test cases...y are they needed?? 

Prakhar Jain:
20111210 18:27:53
prob is too hard to understand and the trivial sample test case contributes to it greatly......:(


fitcat:
20110829 03:07:25
Numbers mean natural numbers?


hunter:
20110506 07:14:01
what is the answer for n=5??? 

Kasprov:
20110411 12:52:59
wat will be the answer for N=1....

Added by:  Varun Jalan 
Date:  20100125 
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 