Time Limit: 1 s
Memory Limit: 32 MB

Submission：64
AC：16
Score：99.05

A coach wants to select some people to attend an event.

Since there are too many competitors, they live in *N* hotels (number *1* from *N*) respectively , the number *1* hotel can accommodate *1* guest, the number *2* hotel can accommodate *2* guests...and the number *N* hotel can accommodate *N* guests.

The coach is lazy, he only wants to choose one hotel from number *1* to number *N* selecting *m* people to attend the event. *m* is at least *1* and no more than the total number of competitors in this hotel.

The coach wants you to calculate how many ways exactly he can select people to attend the event. Output the answer modulo 1000000007.

The first line of input is an integer T, which indicates the number of test cases.

T test cases follow. Each test case contains only one integer N where N will be between 1 and 10^9, inclusive. (Reminder, use "long long" to store this number.)

You should output T lines exactly. Each line contains the total ways the coach can choose (modulo 1000000007).

input

5
1
2
3
10
20

output

1
4
11
2036
2097130

N=2, if the coach chooses the number one hotel, only one people, so he only 1 way to choose people. If the coach chooses the number 2 hotel, there are two people (named A,B), so he can chose {A}, {B}, {A,B}. He has 3 way. The total is 4.