Coin Toss
Tag(s):

## Easy, Matrix Exponentiation

Problem
Editorial
Analytics

Bruce becomes very sad when he realises 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 while tossing the coin.

Harvey tosses the coin finite number of times and lists the outcomes. In the list if Tails comes three times in a row, He remebers 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 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

Problem setter : Siddhant

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Codemania 2.0

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Data Structures > Arrays
• Math > Number Theory
• Algorithms > Graphs
• Basic Programming > Input/Output
• Data Structures > Disjoint Data Structures
• Basic Programming > Implementation