Colored Tower of Hanoi

Time limit1sMemory limit1024 MB

Summary

Move a tower of 2N disks, stacked as red and black pairs for sizes 1 to N, from peg 1 to peg 3 in the same order, and count the minimum moves modulo 1e9+7.

Level: Medium7 of 10
Topics: Math, Dynamic programming, Recursion
Solved: No attempts yet

Problem

The Tower of Hanoi game uses 3 pegs and several disks, all of different sizes. At the start, the disks sit on peg 1 in size order, with the largest disk at the bottom. You must move every disk to peg 3 while following these rules.

A larger disk cannot be placed on top of a smaller disk.
You can move only one disk at a time.

Based on these rules, we want to build a version of the game where the disks come in two colors.

At the start, peg 1 holds, from top to bottom: a red disk of size 1, a black disk of size 1, a red disk of size 2, a black disk of size 2, ..., a red disk of size $N$ , and a black disk of size $N$ .

Following the rules above, move the disks so that peg 3 holds, from top to bottom: a red disk of size 1, a black disk of size 1, a red disk of size 2, a black disk of size 2, ..., a red disk of size $N$ , and a black disk of size $N$ . What is the minimum number of moves needed to do this?

Input

The first line contains an integer $N$ ( $1 \le N \le 10^6$ ).

Output

On the first line, print the minimum number of moves. Since the number can be large, print the remainder when the minimum number of moves is divided by $10^9 + 7$ .

Hint

If disks have the same size, you can place either one on top of the other regardless of color. However, the final state must be, from top to bottom: red disk, black disk, red disk, black disk, and so on.

Examples1

Example 1
Input
```
1
```
Expected output
```
3
```