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
paras meena: 2016-11-30 23:00:38

@[bitthal] N >= 1

KD : 2016-06-20 20:34:00

AC in one go :D
my 200th :)

Arpit Gupta: 2016-06-02 19:21:16

Anyone Help... used exponentiation... used ans=1 for n=0 and 1, tests where my code might go wrong ans for n=10 is 512... i got that...
EDIT: Did a silly mistake in precompuation :D

Last edit: 2016-06-02 19:48:33
Arpit Gupta: 2016-06-02 19:18:51

Some sample tests where my program goes wrong... used exponentiation.... for n=0,1 ans=1 also.. even then wrong ans... Help anyone??

cegprakash: 2015-12-13 16:05:13

For those who feel the problem statement is not clear, you have to find the number of permutations such that for all i,j 1<=i<=j<=n the maximum element between the indices [i..j] is either present at index i, or at index j

Last edit: 2015-12-13 19:28:16
prateek goyal: 2015-06-20 12:47:21

no need of permutation and combination

[bitthal]: 2014-08-17 18:22:55

for n=0...ans is 1.
simple maths but test case 0 can costs a lot..

Last edit: 2014-08-17 18:23:52
L: 2014-06-30 13:34:41

if getting TLE use modular arithmetic..
for n=10 ans is 512 .
easy when you understand the question..

Last edit: 2014-06-30 13:35:57
appy: 2014-05-29 16:53:55

More test cases pls

Anubhav Balodhi : 2014-03-14 09:51:15

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


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