F - Candy Retribution

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000

問題文

次の条件を満たす長さ N の非負整数列 A_1, A_2, ..., A_N が何通りあるか求めてください。

  • L \leq A_1 + A_2 + ... + A_N \leq R
  • N 個の要素を降順に並べたとき、上から M 番目と M+1 番目の要素は等しい。

答えは非常に大きくなることがあるので、10^9+7 で割ったあまりを出力してください。

制約

  • 入力はすべて整数
  • 1 \leq M < N \leq 3 \times 10^5
  • 1 \leq L \leq R \leq 3 \times 10^5

入力

入力は以下の形式で標準入力から与えられます。

N M L R

出力

条件を満たす非負整数列の個数を 10^9+7 で割ったあまりを出力してください。


入力例 1

4 2 3 7

出力例 1

105

条件を満たす非負整数列は、

\begin{eqnarray} &(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{eqnarray}

およびこれらの並べ替え,105 通りです。


入力例 2

2 1 4 8

出力例 2

3

条件を満たす非負整数列は (2, 2), (3, 3), (4, 4)3 通りです。


入力例 3

141592 6535 89793 238462

出力例 3

933832916

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.


Sample Input 1

4 2 3 7

Sample Output 1

105

The sequences of non-negative integers that satisfy the conditions are:

\begin{eqnarray} &(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{eqnarray}

and their permutations, for a total of 105 sequences.


Sample Input 2

2 1 4 8

Sample Output 2

3

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


Sample Input 3

141592 6535 89793 238462

Sample Output 3

933832916