思路：动态规划

状态定义：

$dp[i][j]$ 表示前 $i$ 个数，第 $i$ 个数为 $j$ 的方案数。

状态转移： $dp[i][0] = dp[i - 1][1]$

$dp[i][1] = dp[i - 1][0] + dp[i - 1][0]$

题目内容

小红有 $n$ 个数字 $0$ 和 $n$ 个数字 $1$ 。

现在，小红要从这 $2n$ 个数字中选出 $n$ 个数字进行排列。

但是对小红来说，排列中连续出现两个 $0$ 是让他不能接受的。

现在，小红想问你，可以选出多少种不同的排列方式。

输入描述

一行，一个整数 $n(1\leq n\leq 5\times 10^6)$ 表示有 $n$ 个数字 $0$ 和 $n$ 个数字 $1$ 。

输出描述

输出不同排列的方案数，答案对 $10^9 + 7$ 取模。

样例

输入

2

输出

3

说明 00 不符合小红的要求，01, 10, 11 都是符合要求的。共有 $3$ 种。