Score: $1000$ points

Problem Statement

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

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

Since the answer can be enormous, print it modulo $10^9+7$.

Constraints

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of sequences of $N$ non-negative integers, modulo $10^9+7$.

4 2 3 7

105

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, for a total of $105$ sequences.

2 1 4 8

3

The three sequences that satisfy the conditions are $(2, 2)$, $(3, 3)$, and $(4, 4)$.

141592 6535 89793 238462

933832916