Problem Description

Find the number of sequences of non-negative integers $ A_1, A_2, ..., A_N $ of length $ N $ that satisfy the following conditions:

• $L \leq A_1 + A_2 + ... + A_N \leq R$
• When the $ N $ elements are sorted in descending order, the $ M $-th and $ M+1 $-th elements are equal.

Since the answer can be very large, output the answer modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L $ $ R $

Output Format

Output the number of sequences of non-negative integers that satisfy the conditions, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

4 2 3 7

Sample Output #1

105

Sample Input #2

2 1 4 8

Sample Output #2

3

Sample Input #3

141592 6535 89793 238462

Sample Output #3

933832916

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq M < N \leq 3 \times 10^5$
• $1 \leq L \leq R \leq 3 \times 10^5$

Sample Explanation 1

The sequences of non-negative integers that satisfy the conditions are:
$ \begin{aligned}
& (1, 1, 1, 0), (1, 1, 1, 1), (2, 1, 1, 0), (2, 1, 1, 1), (2, 2, 2, 0), (2, 2, 2, 1), \
& (3, 0, 0, 0), (3, 1, 1, 0), (3, 1, 1, 1), (3, 2, 2, 0), (4, 0, 0, 0), (4, 1, 1, 0), \
& (4, 1, 1, 1), (5, 0, 0, 0), (5, 1, 1, 0), (6, 0, 0, 0), (7, 0, 0, 0)
\end{aligned} $
and their permutations, totaling $ 105 $ sequences.

Sample Explanation 2

The sequences of non-negative integers that satisfy the conditions are $ (2, 2), (3, 3), (4, 4) $, totaling $ 3 $ sequences.

见题面 Input 部分

见题面 Output 部分