题目描述

津津、菲菲和皮皮在三亚的海边玩套圈游戏，要求按照Hanoi塔的规则完成。已知在A柱上放有2n个圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：

1. 每次只能移动一个圆盘
2. 三根柱子上的圆盘都要保持上小下大的顺序

对于输入的n，输出完成上述任务所需的最少移动次数Aₙ。

输入格式

一个正整数n，表示在A柱上放有2n个圆盘（n ≤ 1000）。

输出格式

完成上述任务所需的最少移动次数Aₙ。

样例

输入#1

1

输出#1

2

输入#2

2

输出#2

6