Problem Statement

In the mystical land, the wise King has annoying challenge for his subjects. He wants to find the number of magical sequences that hold the key to unlock an ancient treasure. The sequences must follow the following rules: Each sequence consists of N numbers. Each number in the sequence must be between 1 and M, inclusive. The absolute difference between any two consecutive numbers in the sequence must be at least K. King knows that the number of such sequences can be large, so he wants you help to find the count of these sequences modulo 10^9+7. Note: First and last number of Sequence are not adjacent. Absolute of |-7| = 7 i.e absolute of negative number is positive. Input Format The only line of input contains three space separated integers N, M and K denoting the number of the sequence, the range of the sequence and the absolute difference between any two consecutive numbers in the sequence must be at least K respectively. Output Format Print a single integer as a count of such sequen