已知一个数列 $ 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} $