I. KSumT
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tutz likes math problems; this time he is trying to solve the following problem:

You are given $$$K$$$, $$$S$$$, $$$T$$$ and are asked how many sequences of $$$K$$$ integers (more formally $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$\cdots$$$, $$$a_K$$$) follow these rules:

  • $$$a_i \gt 0$$$, for any $$$i$$$ ($$$1 \leq i \leq K$$$)
  • $$$a_1 + a_2 + a_3 + \cdots + a_K = S $$$
  • $$$a_1 \cdot a_2 \cdot a_3 \cdot \ \dots \ \cdot a_T = a_2 \cdot a_3 \cdot a_4 \cdot \ \dots \ \cdot a_{T+1} = \dots = a_{K-T+1} \cdot a_{K-T+2} \cdot a_{K-T+3} \cdot \ \dots \ \cdot a_K$$$

You should find the number of such arrays modulo $$$10^9 + 7$$$ ($$$10^9 + 7$$$ is a prime number).

Input

The first line contains 3 integers $$$K$$$, $$$S$$$, $$$T$$$ ($$$1 \le K, S, T \le 5 \cdot 10^6$$$, $$$K \geq T$$$)

Output

Output one integer — the number of possible sequences modulo $$$10^9 + 7$$$

Examples
Input
5 13 3
Output
15
Input
15 44 9
Output
1162800
Note

The 15 sequences in the first example are: $$$[1, 1, 9, 1, 1]$$$ , $$$[1, 2, 7, 1, 2]$$$ , $$$[1, 3, 5, 1, 3]$$$ , $$$[1, 4, 3, 1, 4]$$$ , $$$[1, 5, 1, 1, 5]$$$ , $$$[2, 1, 7, 2, 1]$$$ , $$$[2, 2, 5, 2, 2]$$$ , $$$[2, 3, 3, 2, 3]$$$ , $$$[2, 4, 1, 2, 4]$$$ , $$$[3, 1, 5, 3, 1]$$$ , $$$[3, 2, 3, 3, 2]$$$ , $$$[3, 3, 1, 3, 3]$$$ , $$$[4, 1, 3, 4, 1]$$$ , $$$[4, 2, 1, 4, 2]$$$ , $$$[5, 1, 1, 5, 1]$$$