Saad has recently found out that his village pond has a lot of bacteria in it and they are increasing every day. After some research he discovered a pattern.

He found out that F_i=F_i-1+2*F_i-2 where F_i denotes the number of bacteria in the i-th day.

He did some more research and figured out that in the beginning there were only 2 bacteria in the pond and in the 2nd day there were 7 bacteria and after that they started increasing maintaining the above relation.

Now saad wants to find the number of bacteria in the n-th day and he needs your help.

Input

First line of the input contains a single integer T (1<=T<=10⁵) denoting the number of test cases.

Then each of the next T lines contains a single integer N (1<=N<=10¹⁸).

Output

For each case print a single integer in a line denoting the number of bacteria in the N-th day. Since the answer can be very large print the answer modulo of 1000000007.

Sample Input

4

3

5

10

1000

Sample Output

11

47

1537

32634809