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).

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, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Math > Linear Algebra
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > String Algorithms
• Algorithms > Graphs