新汉诺塔

题目描述

汉诺塔问题是最经典的递推问题之一：

• 有三个可以放圆盘的柱子，编号为 A、B 和 C；
• 开始时柱子 A 上套着 $n$ 个圆盘，它们从上到下按照从小到大的顺序排列；
• 我们的任务是要把这 $n$ 个圆盘移到柱子 C 上，并保持它们的原有顺序不变；
• 圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入，每次只能移动一个圆盘，小圆盘必须时刻位于大圆盘之上。

小杨在学习了汉诺塔问题后，决定添加一个新规则：每一次移动，圆盘只能从 A 移动到 B，从 B 移动到 C，或者从 C 移动到 A；其它移动是不允许的。在新规则下，给定圆盘数量 $n$，试问最少移动步数是多少？

输入格式

输入一个正整数 $n$，表示圆盘的数量。

输出格式

输出一个整数，表示在新规则下将 $n$ 个圆盘从 A 移动到 C 所需的最少移动步数。

数据范围

对于所有数据，$n \le 20$。

样例

输入样例 1

2

输出样例 1

7

输入样例 2

3

输出样例 2

21