Coder Express Le!!

Thangabali won the contest and Meenamma was not ready to marry him so she ran away with Rahul to a town where Thangabali was trained. The experts helped Rahul in solving the toughest question and help improve his coding skills. As a final challenges:They ask him solutions to some sequences.

The first sequence was : 0 1 1 2 3 5 8 13.....
Rahul easily fugured out and answered it is fibonacci F(n)=F(n-1)+F(n-2) n>=2,and F[n]=1 for n=0,1

The second sequence which they gave were: 1 1 3 7 17...
After thinking for a while Rahul answered it as F(n)=2*F[n-1]+ F[n-2] n>=2,and F[n]=1 for n=0,1

They were very impressed and they asked him to build the solution for the third sequence and then he is well trained to defeat anybody?
The third sequence was 1 1 3 8 20 50 123...and so on

Rahul was unable to figure it out .Your task is to tell him the nth term of the third sequence so that he could easily solve the problem.

Input Specification:

First line contains an integer T(1 < = T< = 1000) that represents the number of test cases.Then follows the T containg the integer N(1< = N< = 1000000000) specifying the term to be printed.

Output Specification:

For each test case, print only one line, the nth term
Since the output would be very large you have to print your answer modulo 1000000007.

Sample input:

3
1
2
3

Sample Output:

1
1
3