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
Anubhav Balodhi : 2014-03-14 09:51:15

Doing too much PnC makes this problem very simple ;-D

god_father: 2012-12-22 13:50:41

very easy move it to tutorial...& n=5 ans is 16.

(Tjandra Satria Gunawan)(曾毅昆): 2012-06-16 19:39:06

optimize I/O, use precomputation, then AC 0.02s :)
good problem...

Aniket Divekar: 2011-12-18 06:17:28

@Varun : what are i and j exactly....they are not in test cases...y are they needed??

Prakhar Jain: 2011-12-10 18:27:53

prob is too hard to understand and the trivial sample test case contributes to it greatly......:(
EDIT:1<=i<=j<=n

Last edit: 2012-01-06 12:34:13
fitcat: 2011-08-29 03:07:25

Numbers mean natural numbers?
What is the definition of i and j?
Permutation of numbers has elements and indices?

hunter: 2011-05-06 07:14:01

what is the answer for n=5???

Kasprov: 2011-04-11 12:52:59

wat will be the answer for N=1....
will it be 0

Anoop Chaurasiya: 2010-11-06 06:03:22

think like a kid!!!!.....:P


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