题目描述

在黑板上写有 $N$ 个 $0$ 和 $M$ 个 $1$。从这个状态开始，我们将重复以下操作：选择黑板上的 $K$ 个有理数并擦除它们，然后在黑板上写一个新数，该数等于这 $K$ 个数的算术平均值。在这里，假设 $N + M - 1$ 能被 $K - 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}$。

例如，如果我们执行以下操作：

• 擦除 $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