#77. 「NOIP 欢乐%你赛」小澳的坐标系

内存限制:128 MiB 时间限制:1000 ms 输入文件:coordinate.in 输出文件:coordinate.out
题目类型:传统 评测方式:文本比较
上传者: Menci

题目描述

小澳的梦境中出现了一个平面直角坐标系,自原点,向四方无限延伸。

小澳在坐标系的原点,他可以向上、向左或者向右走。他可以走 n 步,但不能经过相同的点。

小澳想知道他有多少种走法。

输入格式

输入文件仅第一行一个正整数 n ,表示小澳可以走的步数。

输出格式

输出文件共一行,输出一个正整数,表示答案(对 10 ^ 9 + 7 取模)。

样例

样例输入 1

2

样例输出 1

7

样例输入 2

3

样例输出 2

17

数据范围与提示

测试点编号 n
1 - 2 n \leq 10
3 - 4 n \leq 100
5 - 6 n \leq 1000
7 - 8 n \leq 10 ^ 6
9 - 10 n \leq 10 ^ 9