KSumT
Description
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 $
- $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).
The first line contains 3 integers $K$, $S$, $T$ ($1 \le K, S, T \le 5 \cdot 10^6$, $K \geq T$)
Output one integer — the number of possible sequences modulo $10^9 + 7$
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$
5 13 3
15 44 9
15
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]$