← 返回题目列表

AtCoder · agc009_e

E. 永恒的平均值

中文机器翻译题面 查看原题

分数: 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