Easy Money
Practice
3 (3 votes)
Mathematics
Modular arithmetic
Easy Medium
Problem
9% Success 1948 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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}\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
5 votes
Tags:
Easy-Medium
Points:30
21 votes
Tags:
SortingIntegerModulus ArithmeticModulesC++Number TheoryMathematics
Points:30
13 votes
Tags:
MathematicsModular arithmeticEasy-Medium