题目描述

汉诺塔问题大家都已经很熟悉了：有三根柱子，一些大小不同的金片。最开始所有金片按大小顺序叠放在柱子 A 上，要求把所有金片移动到柱子 C，可以借助柱子 B。每次只能移动一个金片，且大金片不能放在小金片上面。

现在给定金片的数量 $n$，请你计算最少需要移动多少次。

输入格式

一行一个整数 $n$，表示金片的数量。

输出格式

一行一个整数，表示最少的移动次数。

样例

3

7

数据范围

• $1 \le n \le 20$