問題文

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

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

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

制約

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

入力

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

$N$ $M$ $K$

出力

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

入力例 1

2 2 2

出力例 1

5

最後に残る有理数としてありうるものは、$\\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}$ を書く。

入力例 2

3 4 3

出力例 2

9

入力例 3

150 150 14

出力例 3

937426930