当前没有测试数据。

题目描述

汉诺塔游戏有三根柱子，从左到右依次记为 A、B、C。

一开始，一共有 $n$ 个大小互不相同的圆盘全部套在最左侧的 A 柱子上。圆盘按照从大到小摆放：最大的圆盘放在最底下，越往上圆盘越小。

移动必须遵守三条规则：

1. 每一次只能移动一个圆盘；
2. 任何时候，都不允许把大圆盘放在小圆盘的上面；
3. 圆盘只能移动到相邻的柱子，不能直接把 A 的盘子移到 C，也不能直接 C 移到 A。

我们要把所有圆盘，全部从柱子 A 移动到最右侧的柱子 C，可以借助中间的 B 柱子临时放圆盘。

请求出完成目标，最少需要移动多少次。

输入格式

输入只有一行，包含一个整数 $n$，代表圆盘的数量。

范围：$1 \le n \le 20$

输出格式

输出一行一个整数，代表最少的移动次数。

样例 #1

样例输入 #1

1

样例输出 #1

2

解释：1 个盘子：A→B，B→C，一共 2 步。

样例 #2

样例输入 #2

2

样例输出 #2

7

样例 #3

样例输入 #3

3

样例输出 #3

21

提示

$1 \le n \le 20$。