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:


Example

decompose.in

decompose.out

Comments

20 2 3

8


The number of kx-decompositions for this case is 8.
These are: 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12