题目描述

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

完整思路

1. 状态定义

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

题目内容

一觉醒来，小$A$发现自己身处一个无限大的平面直角坐标系的原点。坐标系之神告诉他,他可以在这个坐标系内移动,但每一步只能选择上,左,右三个方向之一，并朝着这个方向移动$1$个单位的距离。特别的，坐标系之神要求小$A$不能经过相同的点。

坐标系之神告诉小$A$，只要他能算出走$n$步的合法方案数，就把他放回现实世界。小$A$刚醒来还无法深入思考，想你帮他计算一下结果。

输入描述

输入只有一行，包含$1$个整数$n(1<=n<=1000000000)$

输出描述

一行输出$1$个整数，代表题目所求答案，如果答案过大，请将其对$10^9+7$取模。

注:$10^9+7即1000000007$，取模即求余运算。

样例1

输入

2

输出

7

说明

从$(0,0)$出发走$2$步,共$7$种合法走法:

$(0,0)->(0,1)->(0,2)$

$(0,0)->(0,1)->(1,1)$

$(0,0)->(0,1)->(-1,1)$

$(0,0) ->(1,0)->(2,0)$

$(0,0)->(1,0)->(1,1)$

$(0,0) ->(-1,0)->(-2,0)$

$(0,0) ->(-1,0)->(-1,1)$