新汉诺塔

题面描述

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

有三个可以放圆盘的柱子，编号为、和。

开始时柱子上套着个圆盘，它们从上到下按照从小到大的顺序排列。

我们的任务是要把这个圆盘移到柱子上，并保持它们的原有顺序不变。

在移动圆盘的过程中，需要遵守以下规则：

1. 圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入。
2. 每次只能移动一个圆盘。
3. 小圆盘必须时刻位于大圆盘之上。

小杨在学习了汉诺塔问题后，决定添加一个新规则：

1. 每一次移动，圆盘只能从移动到，从移动到，或者从移动到；其它移动是不允许的。

在新规则下，给定圆盘数量，试问最少移动步数是多少？

输入格式

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

输出格式

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

样例1

输入：

2

输出：

7

样例解释1

以下步骤是最佳的（编号为1的是小盘，为2的是大盘）：

1. 将1从移动到；
2. 将1从移动到；
3. 将2从移动到；
4. 将1从移动到；
5. 将2从移动到；
6. 将1从移动到；
7. 将1从移动到。

可以证明没有更少步骤可以完成这个任务。

样例2

输入：

3

输出：

21

数据范围

对于所有数据，

时间限制

1.0 s

内存限制

512.0 MB