题目描述

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

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

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

输入格式

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

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

输出格式

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

题目大意

求满足以下条件的非负整数序列 $\{a_{1..N}\}$ 个数：

1.$\sum a_i\in[L,R]$。

2.将序列降序排列后，第 $M$ 位的数等于第 $M+1$ 位的数。

由于答案很大，输出序列个数模 $10^9+7$ 后的结果。

4 2 3 7

105

2 1 4 8

3

141592 6535 89793 238462

933832916

提示

制約

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

Sample Explanation 1

条件を満たす非負整数列は、 $ \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$ 通りです。

Sample Explanation 2

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