You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

琪亚娜

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

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

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

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

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

去吧这个不完美的故事

变成你所期望的样子

活下去，琪亚娜

这就是，最后一课了

Description

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

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

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

Format

Input

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

Output

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

Samples

2

3

3

7

Limitation

1s, 1024KiB for each test case.