Coin Toss
/

## Matrix Exponentiation

Problem
Editorial
Analytics

Bruce is very sad after being informed that Harvey is now killing people based on the outcome of a coin toss. He also knows that Harvey kills someone only when he remembers Rachel after tossing the coins.

Harvey tosses the coin finite number of times and lists the outcomes. In the list if Tails comes three times in a row, He remembers Rachel and kills the other person.

Bruce is sad but wants to focus on positives. so he thinks about the number of ways when the other person is $not$ killed for given number of tosses. As he is unable to compute the desired number he asks you to do so.

$Input :$

First line of the Input contains an integer T denoting the number of testcases. Each testcase contains only one integer N denoting the number of times Harvey tosses the coin.

$Output :$

print a single integer denoting the answer%1000000007.

$Constraints$ :

1<= T <= 10^5

1<= N <= 10^18

SAMPLE INPUT
2
4
5
SAMPLE OUTPUT
13
24
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...