Problem Statement

An old archive describes a vault that only opens for sequences meeting a strange set of rules. The vault's keeper wants to know how many such sequences exist. A qualifying sequence must satisfy: 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. Since this count can grow enormous, report it modulo 10^9+7 instead. 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 sequences. Constraints 2<=N<=10^4 1<=M<=5*10^4 0<=K<=M-1 Sample Testcase 1 Tes