0012 - カタラン数

Problem

問題文

整数Nが与えられるので、カタラン数$c_N$を$10^9+7$で割った余りを計算してください。 $c_N$は、長さ2Nの対応の取れた括弧列の個数です。

制約

$0 \le N \le 100000$
満点は100点です。

入出力例

入力例 1

3

出力例 1

5
長さ6の対応の取れた括弧列は、((()))、(())()、(()())、()(())、()()()の5種類です。

入力例 2

1000

出力例 2

110961515