Problem 1898: I. KSumT

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

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