## 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 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^{5}) denoting the number of test cases.

Then each of the next T lines contains a single integer N (1<=N<=10^{18}).

**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

hide comments

[Rampage] Blue.Mary:
2016-04-05 03:45:45
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. |

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 |