BUZZOFF - Buzz Trouble

no tags 

Commander Nebula decided to take interns into Star Command to join the Little Green Men (LGMs). And the job of physical training of these LGMs went to Buzz Lightyear. Assume N interns are taken, each with a distinct LGM ID.

Being busy with XR, Buzz sent Mira Nova to select a few of the interns and line them in the training center. XR noticed that he neither told Mira how many LGMs to select, nor in which order to arrange them; so Mira can select any number M of students (1<=M<=N) and line them up randomly (Assume that if Mira is to select M LGMs, then she selects the M smallest LGM IDs, eg, if N=5 and IDs be 12, 3, 4, 11, 2 and she decided to select 3 LGMs, then she picks up 3, 4 and 2).

XR wonders, how many different arrangements might Buzz find on arriving in the training centre for which no LGM is more than unit distance away from its correct position, and Buzz has to do less work in ordering them correctly (in increasing order of LGM ID).

As result might be large, output result modulo 10^9+7 (1000000007)

Input

first line contains T, number of test cases

Next T lines contain single number N, indicating number of LGM interns.

Output

T lines, each with the answer for corresponding case.

Constraints

1<=T<=10^4

1<=N<=10^18

Example

Input:
5
1
2
5
8
10
 
Output:
1
3
19
87
231

Explanation

for N=1, only case is to pick the only LGM.

for N=2, and LGM IDs are say 1 and 2, then Buzz might find [1], [1, 2], or [2, 1] Therefore 3.


hide comments
Pathan Salman Khan: 2014-12-30 07:46:31

I have tried O(logN), recursion with memoization, and only 1 level of function, but still I am getting TLE. Can someone please help me out?

I need tips for improving:

1). Modulo operation
2). Multiplication
3). Creating new pointers

Last edit: 2014-12-30 10:21:18
Venkatesh Ganesan: 2014-01-29 22:02:26

time limit is too strict. had to do ugly optimizations for AC.

Ankit Kumar: 2013-12-22 02:11:35

[spoilers removed]

Last edit: 2013-12-22 02:11:31

Added by:Piyush Kumar
Date:2012-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All