No.727 仲介人moko
タグ : / 解いたユーザー数 79
作問者 : moko / テスター : square1001
問題文
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もしくは右上の雲マークをクリックしてアカウントを作成してください。