/ 
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{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}
およびこれらの並べ替え，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{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.
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