已知一个数列 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 取模后的结果。
已知一个数列 f(1), f(2), f(3), \dots 满足以下递推关系：
给定一个正整数 x ，请计算 f(x) 的值。由于答案可能非常大，你只需要输出它对 10^9 + 7 取模后的结果。
输入只有一行，包含一个整数 x （ 4 \le x \le 10^{18} ）。
输出一个整数，表示 f(x) \bmod (10^9+7) 的值。
4
4
7
34
100
530643758
f(4) = f(3) + 2 \times f(2) + f(1) = 1 + 2 \times 1 + 1 = 4 。
数列前几项为：1, 1, 1, 4, 7, 16, 34, ...，因此 f(7) = 34 。