All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Coin Toss
Tag(s):

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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIIT Allahabad

Challenge Name

Codemania 2.0

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?