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
piyush490:
20180616 21:54:00
Use modular exponentiation. 

paras meena:
20161130 23:00:38
@[bitthal] N >= 1


KD :
20160620 20:34:00
AC in one go :D


Arpit Gupta:
20160602 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...


Arpit Gupta:
20160602 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:
20151213 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: 20151213 19:28:16 

prateek goyal:
20150620 12:47:21
no need of permutation and combination 

[bitthal]:
20140817 18:22:55
for n=0...ans is 1.


L:
20140630 13:34:41
if getting TLE use modular arithmetic..


appy:
20140529 16:53:55
More test cases pls

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 