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 > 0$, for any $i$ ($1 \leq i \leq K$)
• $a_1 + a_2 + a_3 + \cdots + a_K = S$
• All subarrays of length $T$ have the same product. More formally, $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 data

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

Output data

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

Example 1

stdin

5 13 3

stdout

15

Explanation

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]$

Example 2

stdin

15 44 9

stdout

1162800