配点: $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$ で割ったあまりを出力してください。

4 2 3 7

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 1 4 8

3

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

141592 6535 89793 238462

933832916