← 返回题目列表

AtCoder · jsc2019_qual_f

F. 糖果报应

中文机器翻译题面 查看原题

分数: 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