← 返回 apple 的题目列表Tower of Hanoi (Recursion)
类型：online_judge
Problem: Tower of Hanoi (recursion)
Given an integer n (1 ≤ n ≤ 20), representing the number of disks. All disks are stacked on peg A from smallest to largest. You need to move all disks to peg C following the rules:
Move only one disk at a time.
Never place a larger disk on top of a smaller one.
Output the minimum number of moves required.
Input
One integer n.
Output
One integer: the minimum number of moves.
Constraints
1 ≤ n ≤ 20
Example
Input:
3
Output:
7
Example
Input
1
Output
1