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.
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).
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.
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.