Problem G : Decompose
For any three natural numbers, n, k and x, we call a kx-decomposition of number n a posibility of writing the n number as a sum of k non-null numbers so as the difference between any two terms of the sum to be at least x.
Given three numbers, n,k and x, determine how many distinct kx-decompositions exist. Two decompositions are considered distinct is they differ by at least one term.
Input:
Read from the standard input three non-null natural numbers, n, k and x, separated by one white space.
Output:
Write on the standard output a single value representing the reminder of the division of the number of kx-decompositions by 10007
Notes:
20% of the datasets are going to have 0 < n ≤ 200; 80% are going to have 200 < n ≤ 10000
1 ≤ x,k ≤ n
Time limit: 3s
Example
decompose.in |
decompose.out |
Comments |
20 2 3 |
8
|
The number of
kx-decompositions for this case is 8. |