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.