AT_agc009_e [AGC009E] Eternal Average

黑板上写有 $N$ 个 $0$ 和 $M$ 个 $1$。从这个状态开始，你可以重复进行如下操作：从黑板上写着的有理数中选出 $K$ 个并将它们擦去，然后把这 $K$ 个有理数的平均数重新写到黑板上。 但要求 $N+M-1$ 能被 $K-1$ 整除。 当无法再进行操作时，黑板上最终只会剩下一个有理数。 请你求出，作为最后剩下的有理数，其可能取值的个数对 $10^9+7$ 取模后的结果。

输入为一行，包含三个整数： > $N$ $M$ $K$

输出最后可能剩下的有理数的取值个数，对 $10^9+7$ 取模后的结果。

## 限制 - $1 \leq N, M \leq 2000$ - $2 \leq K \leq 2000$ - $N+M-1$ 能被 $K-1$ 整除。 ## 样例解释 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}$。 由 ChatGPT 4.1 翻译