题目描述

黒板に、$N$ 個の $0$ と $M$ 個の $1$ が書かれています。 この状態から、黒板に書かれている有理数のうち $K$ 個を選んで消し、それら $K$ 個の有理数の平均を新たに書き加える操作を繰り返します。 ただし、$N+M-1$ は $K-1$ で割り切れるものとします。

このとき、操作ができなくなるまでこの操作を繰り返すと最終的に黒板には $1$ つの有理数が書かれた状態になります。

この残った有理数の値としてありうるものの個数を $10^9\ +\ 7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

输出格式

最後に残った有理数の値としてありうるものの個数を $10^9\ +\ 7$ で割ったあまりを出力せよ。

题目大意

黑板上有 $n$ 个 $0$ 和 $m$ 个 $1$，我们每次选择 $k$ 个数字将其擦除，然后把它们的平均数写上去，这样一直操作直到只剩下一个数字，问剩下的这个数字有多少种不同的情况。

答案对 $10^9+7$ 取模。

$1 \leq n,m \leq 2000,2 \leq k \leq 2000$

保证 $n+m-1$ 能被 $k-1$ 整除。

2 2 2

5

3 4 3

9

150 150 14

937426930

提示

制約

• $1\ ≦\ N,\ M\ ≦\ 2000$
• $2\ ≦\ K\ ≦\ 2000$
• $N+M-1$ は $K-1$ で割り切れる。

Sample Explanation 1

最後に残る有理数としてありうるものは、$ \frac{1}{4},\ \frac{3}{8},\ \frac{1}{2},\ \frac{5}{8},\ \frac{3}{4} $ の $5$ 通りです。 例えば $\frac{3}{8}$ は、以下のような操作で最後に残ります。 - $0,1$ を消して $\frac{1}{2}$ を書く。 - $\frac{1}{2},1$ を消して $\frac{3}{4}$ を書く。 - $0,\frac{3}{4}$ を消して $\frac{3}{8}$ を書く。