{"raw_statement":[{"iden":"problem statement","content":"How many ways are there to arrange $N$ white balls and $M$ black balls in a row from left to right to satisfy the following condition?\n\n*   For each $i$ $(1 \\leq i \\leq N + M)$, let $w_i$ and $b_i$ be the number of white balls and black balls among the leftmost $i$ balls, respectively. Then, $w_i \\leq b_i + K$ holds for every $i$.\n\nSince the count can be enormous, find it modulo $(10^9 + 7)$."},{"iden":"constraints","content":"*   $0 \\leq N, M \\leq 10^6$\n*   $1 \\leq N + M$\n*   $0 \\leq K \\leq N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$"},{"iden":"sample input 1","content":"2 3 1"},{"iden":"sample output 1","content":"9\n\nThere are $10$ ways to arrange $2$ white balls and $3$ black balls in a row, as shown below, where `w` and `b` stand for a white ball and a black ball, respectively.\n`wwbbb` `wbwbb` `wbbwb` `wbbbw` `bwwbb` `bwbwb` `bwbbw` `bbwwb` `bbwbw` `bbbww`\nAmong them, `wwbbb` is the only one that does not satisfy the condition. Here, there are $2$ white balls and $0$ black balls among the $2$ leftmost balls, and we have $2 > 0 + K = 1$."},{"iden":"sample input 2","content":"1 0 0"},{"iden":"sample output 2","content":"0\n\nThere may be no way to satisfy the condition."},{"iden":"sample input 3","content":"1000000 1000000 1000000"},{"iden":"sample output 3","content":"192151600\n\nBe sure to print the count modulo $(10^9 + 7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}