/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
黒板に、N 個の 0 と M 個の 1 が書かれています。 この状態から、黒板に書かれている有理数のうち K 個を選んで消し、それら K 個の有理数の平均を新たに書き加える操作を繰り返します。 ただし、N+M-1 は K-1 で割り切れるものとします。
このとき、操作ができなくなるまでこの操作を繰り返すと最終的に黒板には 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} の 5 通りです。
例えば \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
Score : 1600 points
Problem Statement
There are N zeros and M ones written on a blackboard. Starting from this state, we will repeat the following operation: select K of the rational numbers written on the blackboard and erase them, then write a new number on the blackboard that is equal to the arithmetic mean of those K numbers. Here, assume that N + M - 1 is divisible by K - 1.
Then, if we repeat this operation until it is no longer applicable, there will be eventually one rational number left on the blackboard.
Find the number of the different possible values taken by this rational number, modulo 10^9 + 7.
Constraints
- 1 ≦ N, M ≦ 2000
- 2 ≦ K ≦ 2000
- N + M - 1 is divisible by K - 1.
Input
The input is given from Standard Input in the following format:
N M K
Output
Print the number of the different possible values taken by the rational number that will be eventually left on the blackboard, modulo 10^9 + 7.
Sample Input 1
2 2 2
Sample Output 1
5
There are five possible values for the number that will be eventually left on the blackboard: \frac{1}{4}, \frac{3}{8}, \frac{1}{2}, \frac{5}{8} and \frac{3}{4}.
For example, \frac{3}{8} can be eventually left if we:
- Erase 0 and 1, then write \frac{1}{2}.
- Erase \frac{1}{2} and 1, then write \frac{3}{4}.
- Erase 0 and \frac{3}{4}, then write \frac{3}{8}.
Sample Input 2
3 4 3
Sample Output 2
9
Sample Input 3
150 150 14
Sample Output 3
937426930