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}$