#YAPP. Yet Another Permutations Problem
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</p>Sample Output: 2
Constraints
1 <= T <= 10000
1 <= N <= 1000000000