No.1044 正直者大学

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 100
作問者 : SuunnSuunn / テスター : cureskolcureskol
14 ProblemId : 3621 / 出題時の順位表
問題文最終更新日: 2020-05-01 21:50:20

問題文

 高橋くんは正直者大学(略称:直大)の学生です。

 今日は、正直者大学と嘘つき大学(略称:嘘大)の間での交流パーティーがあります。パーティには正直者大学から高橋くんを含めて$N$人、嘘つき大学から$M$人の学生が参加します。

 交流パーティの最初には、$N+M$人の学生全員が円形に並び、一人ずつ右隣の参加者を紹介します。紹介では、必ず紹介される学生がどちらの大学に所属しているかが発表されますが、紹介する学生が正直者大学に所属しているときは正しく、紹介する学生が嘘つき大学に所属しているときは紹介される学生の実際の所属とは逆に発表されます。

 高橋くんは正直者が多いと嬉しいので、自分が紹介した学生を含めてパーティで$K$人以上が正直者大学に所属していると発表されると嬉しくなります。高橋くんは正直者なので、発表を疑うことはありません。高橋くんが嬉しくなる発表の組み合わせの数を$1000000007$で割ったあまりを求めてください。ただし、$2$つの発表の組み合わせが異なるとは、ある学生が存在して、その学生が紹介する学生が異なることを意味しており、発表の順序には関係ないことに注意してください。

入力

$N\ M\ K$

$1 \le N,M \le 10^5$
$0 \le K \le 2 \times 10^5$
$K \le N+M$

出力

高橋くんが嬉しくなるような並び方の数を$1000000007$で割ったあまりを出力してください。

サンプル

サンプル1
入力
1 1 0
出力
1

並び方は$1$通りしかありません。

サンプル2
入力
2 2 1
出力
4

サンプル3
入力
765 346 315
出力
716277124

(21:49訂正 716177124→716277124 Sampleが誤っており申し訳ございません。)

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