1223: Hanoi塔问题（方案数）

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：1 Solved：1

Description

Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：

(1)一次只能移一个圆盘；

(2)圆盘只能在三个柱上存放；

(3)在移动过程中，不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？



Input

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

Output

移动盘次。

Sample Input Copy 

3

Sample Output Copy 

7

HINT

1<=n<=30