BCTRA - Bacteria in The Pond

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 Fi=Fi-1+2*Fi-2 where Fi 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<=105) denoting the number of test cases.

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

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


Added by:Nashir Ahmed
Date:2016-04-04
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-04-05 03:45:45 [Rampage] Blue.Mary
See problem SEQ. It already exists numerous of this kind of simple recursive (and matrix multiplication) problems at SPOJ. Problem needs to be moved to tutorial section.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.