713. Tower of Hanoi — Minimum Moves (Modulo 10^9+7)

In the classic Tower of Hanoi puzzle, you have three rods and n disks of different sizes which can slide onto any rod. The puzzle starts with the disks stacked on the first rod in decreasing size order (largest at the bottom). The objective is to move the entire stack to the third rod, obeying these rules:
1. Only one disk can be moved at a time.
2. Each move takes the upper disk from one rod and places it on another rod.
3. No disk may be placed on top of a smaller disk.

Given n, return the MINIMUM number of moves required to solve the puzzle, modulo 10^9 + 7. (The exact value is 2^n − 1, which can be very large; return it modulo 1000000007.) Derive the result using the standard recursive Tower of Hanoi formulation combined with modular arithmetic.

Input: A single integer n (number of disks).

Output: Return an integer equal to (2^n - 1) mod (10^9 + 7).

Examples

Input: 1
Output: 1
Explanation: Move the single disk directly: 1 move. 1 mod (10^9+7) = 1.

Input: 2
Output: 3
Explanation: Top -> aux, bottom -> dest, top -> dest = 3 moves.

Input: 3
Output: 7
Explanation: Classic 3-disk solution requires 2^3 - 1 = 7 moves.

Constraints

• 1 <= n <= 10^5

Asked by