781. Tower of Hanoi — General N Disks (Modulo 10^9+7)

Given n disks, return the minimum number of moves to solve the Tower of Hanoi puzzle with 3 pegs, modulo 10^9 + 7. The answer is (2^n - 1) mod (10^9 + 7). Derive this using the recursive formulation T(n) = 2*T(n-1) + 1. Use recursive fast power for efficient computation.

Input: A single non-negative integer n.

Output: Return an integer mod 10^9 + 7.

Examples

Input: 3
Output: 7
Explanation: 2^3 - 1 = 7.

Input: 0
Output: 0
Explanation: No disks, no moves.

Input: 10
Output: 1023
Explanation: 2^10 - 1.

Constraints

• 0 <= n <= 10^4

Asked by