已知一个数列 f(1), f(2), f(3), \dots 满足以下递推关系：

• f(1) = 1
• f(2) = 1
• f(3) = 1
• 对于 x > 3 ，有： f(x) = f(x-1) + 2 \times f(x-2) + f(x-3)

给定一个正整数 x ，请计算 f(x) 的值。由于答案可能非常大，你只需要输出它对 10^9 + 7 取模后的结果。

输入只有一行，包含一个整数 x （ 4 \le x \le 10^{18} ）。

输出一个整数，表示 f(x) \bmod (10^9+7) 的值。

样例1解释

f(4) = f(3) + 2 \times f(2) + f(1) = 1 + 2 \times 1 + 1 = 4 。

样例2解释

数列前几项为：1, 1, 1, 4, 7, 16, 34, ...，因此 f(7) = 34 。

数据范围与约定

• 4 \le x \le 10^{18}