0992 - 集産主義

問題

{0, 1, 2, 3, ... , N-1, N}という配列Aがある。
たとえば、N = 1 なら、 A = {0, 1} である。
配列の順番通りに "0 + 1 + 2 + ... + N-1 + N" とした時、次のように丸カッコで区切る。
この時のカッコの区切り方の総数Sを出力せよ。下にしてよい区切り方としてはいけない区切り方の例を示す。

してよい区切り方
　( 0 + 1 )
　( 0 + ( ( 1 + 2 ) + 3 ) )

してはいけない区切り方
　( 0 + 1 + 2 )
　( 0 + ( 1 ) )

なお、値は非常に大きな数になりうるので MOD = 10⁹ + 7 を用いること。
また、N=0の時、S=1として考えてよい。

入力

N

出力

S

区切り方の総数Sを出力する。
最後に改行すること。

制約

$1 \leq N \leq 8100$
$N$は整数

テストケース

例1

入力

1

出力

1

例2

入力

2

出力

2

( 0 + ( 1 + 2 ) )
( ( 0 + 1 ) + 2 )
の2通りである。

例3

入力

3

出力

5

( 0 + ( 1 + ( 2 + 3 ) ) )
( 0 + ( ( 1 + 2 ) + 3 ) )
( ( 0 + 1 ) + ( 2 + 3 ) )
( ( 0 + ( 1 + 2 ) ) + 3 )
( ( ( 0 + 1 ) + 2 ) + 3 )
の5通りである。