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.

Examples

Input

4 2 3 7

Output

105

Input

2 1 4 8

Output

3

Input

141592 6535 89793 238462

Output

933832916

见题面

见题面