We define a good array as an array of length ~N~ with all elements ranging from ~1~ to ~K~ inclusive, the first element of the array is equal to ~1~, and the last element of the array is equal to ~X~, and consecutive elements must be different from each other.

Given ~N~, ~K~, and ~X~, how many good arrays can you form, mod ~1000000007~?

Input Specification

One line containing ~N~, ~K~, ~X~, the constraints of a good array.

Subtask 1 [30%]

~1 \leq K \leq N \leq 10^3~

~1 \leq X \leq K~

Subtask 2 [70%]

~1 \leq K \leq N \leq 10^5~

~1 \leq X \leq K~

Output Specification

One integer, the number of good arrays that you can form, mod ~1000000007~.

Sample Input 1

4 3 2

Sample Output 1

3

Sample Explanation 1

The good arrays you can form are ~1212~, ~1312~ and ~1232~.

Sample Input 2

77 73 37

Sample Output 2

124047187