Background

琪亚娜

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

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

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

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

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

去吧这个不完美的故事

变成你所期望的样子

活下去，琪亚娜

这就是，最后一课了

Description

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

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

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

Format

Input

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

Output

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

Samples

2

3

3

7

Limitation

1s, 1024KiB for each test case.