Background

Direct Path to the Sky Road · Xiao A’s Adventure, Part IV.

Problem Description

With your help, Xiao A has collected valuable data and finally reached the legendary Sky Mountain that connects to the Sky Road. However, there is still some distance to the Sky Road, and Xiao A suddenly realizes he has no map. Fortunately, he finds a treasure chest at the foot of the mountain. Based on experience (does Xiao A even have any?), he judges that the map should be inside.

On the chest, there are three pegs and $n$ disks stacked on one peg. After a long time thinking, Xiao A concludes that this is the Tower of Hanoi. Moving takes time, so he must brew a longevity potion to complete the task. Now, he asks you to tell him how many steps are needed, so that he can brew enough potion.

Input Format

A single integer $n$, the number of disks.

Output Format

A single integer $s$, the number of steps required.

31

2147483647

15

32767

Hint

Constraints

For all testdata, $n \le 15000$.

Translated by ChatGPT 5