問題一覧 > 通常問題

No.727 仲介人moko

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 216 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : mokomoko / テスター : square1001square1001
5 ProblemId : 2249 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-08-27 17:36:13

問題文

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。