题目描述

在一个无限大的平面直角坐标系中，机器人从原点出发，每一步只能向“上”、“左”、“右”三个方向之一移动 1 个单位，且不允许经过相同的点。求机器人恰好走到第 $n$ 步时的合法走法总数。由于结果可能很大，需对 $10^9+7$ 取模输出。

完整思路

状态定义
- 令 $a_n$ 表示恰好走 $n$ 步的合法路径总数。
- 令 $b_n$ 表示恰好走 $n$ 步，且第 $n$ 步是水平移动（“左”或“右”）的路径数。

在一个无限大的二维网格中，一个机器人从原点 $(0,0)$ 出发。每一步，机器人可以选择向北、向东或向西移动一个单位距离，但决不能踏入任何已经到达过的格子。换句话说，路径上的所有格点必须互不相同。

给定一个整数步数 $n$ ，请你计算所有可能的合法行走路径的数量。由于答案可能十分巨大，请输出答案对 $10^9+7$ 取模后的结果。

步数 $n$ 满足 $1 \le n \le 10^9$ 。

输入仅有一行，包含一个整数 $n$ ，表示需要行走的步数。