#P1176. D.我已经做出了我的选择

D.我已经做出了我的选择

Background

琪亚娜

当你醒来,会看到一切都变了

你会发现,这个世界不再美好

那些平凡的日常,都将一去不会

但是,不要放弃,永远不要放弃

琪亚娜,抬起头,继续前进吧

去吧这个不完美的故事

变成你所期望的样子

活下去,琪亚娜

这就是,最后一课了

img

Description

身负重伤的姬子老师让琪亚娜通关汉诺塔,才能拯救她,琪亚娜现在把这个重任交给你了。

ps:(汉诺塔) 开始有三根柱子,第一根上面放了n个圆盘,其他两根是空的,,圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

现在请输出琪亚娜如果要完成这个游戏需要多少次圆盘移动的操作

Format

Input

第一行输入第一根柱子圆盘的个数n(1<=n<=1000000000)(1<=n<=1000000000)

Output

输出移动的操作次数(由于数字较大所以模134217728输出)

Samples

2
3
3
7

Limitation

1s, 1024KiB for each test case.