No.727 仲介人moko

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 216 MB / 通常問題
タグ : / 解いたユーザー数 44
作問者 : mokomoko / テスター : square1001square1001
2 ProblemId : 2249 / 出題時の順位表

問題文

mokoはとある国の仲介人です。品物を売りたい人と買いたい人とを仲介する仕事をしています。

今日品物をmokoの元で売買する予定の人は$2N$人おり、そのうち半数が品物を売りたい人、半数が買いたい人です。


mokoは品物を売りに来た人から引き取り、買いたい人が来るまでそれを持ち続け、買いに来た人に渡します。

品物を売りたい人は売ろうとしている品物を売りに来ますが、品物を買いたい人は買いに来た時点でmokoが持っている品物の中からランダムに1つ選んで買います。
売りたい人が1度だけ売り、品物はそれぞれの売りたい人によって異なります。

また、品物を売りたい人はいつでもmokoの元を訪れることができますが、品物を買いたい人はmokoが品物を1個以上持っている時しか訪れません。

mokoは仕事の見通しを立てるため、「品物の取り引きの流れ」でありえる組み合わせの数を知りたいと思い、競プロのプロであるあなたに依頼して来ました。

mokoの代わりに「品物の取り引きの流れ」の組み合わせの数を1000000007で割った余りを求めてください。

入力

$N$

$1 \le N \le 10^6$

出力

答えを1行で出力してください。また、最後に改行してください。

サンプル

サンプル1
入力
1
出力
1

売りたい人が1人、買いたい人が1人います。
買いたい人は売りたい人がmokoに品物を引き渡してからしか買いに来ることができないので、
売りたい人 -> 買いたい人
の1通りとなります。

サンプル2
入力
2
出力
12

○を売りたい人、△を買いたい人、□を品物とすると、上の図のようになります。
○や△の中の数字は、売りたい・買いたい人を区別するため。□の数字は品物の番号です。時系列は画像の左から右である。

サンプル3
入力
1333
出力
871035815

1000000007で割った余りを出力することに注意してください。

サンプル4
入力
28880
出力
593741191

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。