解题思路

题意概括： 小 A 从原点 $(0,0)$ 出发，在无限大的平面直角坐标系中，每一步只能走 上、左、右 三个方向之一，步长为 1。要求走的过程中 不能到达已经到过的点。给定步数 $n$，求走恰好 $n$ 步的合法方案数，结果对 $10^9+7$ 取模。 样例：$n=2$ 时共有 7 种，题面已给出。

1. 关键性质分析

1. 没有“下”这个方向，所以纵坐标 $y$ 永远不降低，只会保持或增加。

题目内容

一觉醒来，小$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)$