题目描述

黑板上写有 $N$ 个 $0$ 和 $M$ 个 $1$。从这个状态开始，你可以重复进行如下操作：从黑板上写着的有理数中选出 $K$ 个并将它们擦去，然后把这 $K$ 个有理数的平均数重新写到黑板上。
保证 $N+M-1$ 能被 $K-1$ 整除。

当无法再进行操作时，黑板上最终只会剩下一个有理数。

请你求出，作为最后剩下的有理数，其可能取值的个数对 $10^9+7$ 取模后的结果。

输入格式

输入为一行，包含三个整数：

$N$ $M$ $K$

输出格式

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

样例 1

输入

2 2 2

输出

5

样例 2

输入

3 4 3

输出

9

样例 3

输入

150 150 14

输出

937426930

说明/提示

限制

• $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 翻译