题目内容

在一个向四周无限延伸的网格平面上，一个智能体从原点 $(0,0)$ 出发。每一步它可以向北、向西或向东移动一个单位长度，但禁止向南移动。同时，整个移动过程中不得踏入任何已经访问过的网格点。

给定一个整数 $n$，你需要计算该智能体恰好行走 $n$ 步后，一共有多少种不同的合法路径。

由于答案可能非常庞大，请将结果对 $10^9+7$ 取模后输出。

约束：$n$ 满足 $1 \le n \le 10^9$。

输入描述

输入仅包含一行，一个整数 $n$ $(1 \le n \le 10^9)$。

输出描述

输出一个整数，表示合法路径总数对 $10^9+7$ 取模后的结果。

样例1

输入

1

输出

3

说明

智能体从原点出发，第一步只能向三个允许的方向移动：北、西、东。由于不能向南且不能重复访问已经过的点，因此第一步共有 $3$ 种不同的路径。

样例2

输入

3

输出

17

说明

设 $f(n)$ 表示行走 $n$ 步的合法路径数。通过分析移动约束，可以得到递推关系 $f(n) = 2f(n-1) + f(n-2)$（$n \ge 2$），且边界为 $f(0)=1$，$f(1)=3$。

依此递推：$f(2) = 2 \times 3 + 1 = 7$，$f(3) = 2 \times 7 + 3 = 17$。对 $10^9+7$ 取模后结果仍为 $17$。

样例3

输入

10

输出

8119

说明

继续利用递推公式 $f(n) = 2f(n-1) + f(n-2)$ 或矩阵快速幂即可求出 $n=10$ 时的结果。

依次计算：$f(4)=41$，$f(5)=99$，$f(6)=239$，$f(7)=577$，$f(8)=1393$，$f(9)=3363$，$f(10)=8119$。结果小于 $10^9+7$，取模后直接输出 $8119$。