All Tracks Math Number Theory Problem

Easy Money
Tag(s):

Easy-Medium, Math

Problem
Editorial
Analytics

After spending their last money, three friends Zar, Mas and Ara decided to find a job. They found it, and happily accepted it, not knowing what was coming...

Now they are facing the problem:

There is a fence with $$N$$ pieces. The $$i^{th}$$piece consists of $$2^{i - 1}$$ blocks that they need to color. They have three colors: red, blue and green, and they can only use green to color the whole piece, and red and blue as they wish (see the picture for more details).

picture for the statement

Note that all blocks must be painted.

They need to print the number of possible variations. As the number can be very big, output it modulo $$10^9 + 7$$.

They asked you, the best programmer of Lalalandia, to help them!

Input format

The only line consists of number $$N$$ - the number of fence pieces.

Output format

The only line should contain the answer modulo $$10^9 + 7$$.

Constraints:

$$1 \le N \le 10^{18}$$

SAMPLE INPUT
2
SAMPLE OUTPUT
15
Explanation

With $$N = 2$$, we can paint first piece in 3 colors, and second in 5, so the answer is $$3 * 5 = 15$$.

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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications