该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

现在你通过了进入说唱界的门槛题，但是对于刚进入说唱界的你只可以从底层做起，今天说唱og安排你去搬运蛋糕，看到你梦寐以求的蛋糕口水止不住地流下来，但是首要任务是去搬运蛋糕而不是去吃蛋糕，搬运蛋糕如下： 给你n个蛋糕，以及三个卡车，这些蛋糕最初按大小顺序堆叠在一个卡车上。目标是将所有蛋糕移动到另一个卡车上，遵循两个规则：一次只能移动一个蛋糕，且在移动过程中较大的蛋糕不能放在较小的蛋糕上面。现在og知道你的学历不一般，所以让你计算一下需要移动多少次？次数可能很大，对1e9+7取余。

Format

Input

给你一个整数N，代表蛋糕的数量。 $0\leq N\leq1e9$ .

Output

输出一个整数，需要移动多少次？

Samples

3

7

Limitation

1s, 1024KiB for each test case.