题目描述

汉诺塔的问题大家都已熟悉：有A、B、C三根柱子，初始时A柱上有n个大小不一的金片（大的金片在下方，小的在上方）。需要将所有金片从A柱移动到C柱，移动过程中可借助B柱，且需遵守每次只能移动一个金片、大的金片不能压在小的金片上面的规则。请计算n个金片时，完成移动所需的最少次数。

输入格式

一行一个整数n，代表金片的数量，满足n≤20。

输出格式

一行一个整数，代表n个金片完成移动的最少次数。

样例输入

3

样例输出

7