分数: 1600 点
问题陈述
有 N 零和 M 写在黑板上。 从这个状态开始,我们会重复下面的操作: select 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}.
例如, \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