Jenga 是一款发明于 20 世纪 70 年代的棋盘游戏。在该游戏中，玩家使用木条，每根木条的长度恰好是其宽度的三倍，高度约为其宽度的一半。游戏使用这些木条搭建一座塔，每层由三根木条组成，且下一层的木条与上一层的木条垂直放置。随后，两名玩家轮流从塔中抽出一根木条，并将其垂直于顶层木条的方向放置在顶层。在某个时刻，塔会变得不稳定并在自身重力作用下坍塌。在导致塔坍塌的操作之后进行操作的玩家即为输家。下图展示了经过若干次移动后的塔的示例。

如果一座塔除顶层外，每一层都至少包含两根木条，或者包含一根位于该层中间的木条，则称该塔是稳定的。请你计算由恰好 $n$ 根木条组成的稳定塔有多少种。如果两座塔不能通过绕垂直于底座表面的轴旋转来重合，则认为它们是不同的。

输入格式

输入仅包含一行，为一个整数 $n$ —— Jenga 木条的数量。

$1 \le n \le 10^{18}$

输出格式

输出一个整数 —— 得到稳定 Jenga 塔的方案数。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

1

样例输出 1

1

样例输入 2

42

样例输出 2

729888649

样例输入 3

2

样例输出 3

4