分数: 1000 点
问题陈述
查找序列的数量 N 非负整数 A_1, A_2, ..., A_N 满足以下条件:
- L \leq A_1 + A_2 + ... + A_N \leq R
- 当 N 元素按非升序排序, M-th 和 (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
输出
打印序列数 N 非负整数,模 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
141592 6535 89793 238462
示例输出 3
933832916