← 返回题目列表

AtCoder · tessoku_book_bx

A76. 过河

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

配点: 1000 点

注意

根据书籍的版本,书中的代码可能不正确。请参阅勘误表。

問題文

河流宽度为 KYOPRO 河为 W 米。 N 脚手架从西边开始排成一条直线。 它们的编号最大为 1 减去 N 。脚手架 i (1 \leq i \leq N) 来自西岸 位于 X_i 米处。

太郎决定通过向东方向反复跳跃,从西岸移动到东岸。不过,一跳的距离既不太长,也不太短; L 米或以上 R 米。一共有多少种方式?

制約

  • 1 \leq N \leq 150{,}000
  • 0 < X_1 < X_2 < \cdots < X_N < W \leq 10^{9}
  • 1 \leq L \leq R \leq W

入力

输入是按以下格式从标准输入给出的。

N W L R
X_1 X_2 \ldots X_N

出力

答案 请打印除以 1{,}000{,}000{,}007 后的余数。


入力例 1

5 65 7 37
5 15 30 50 55

出力例 1

7