AtCoder Grand Contest 009
C
Division into Two
AtCoder
⌀ 2437
原题
← BD →
翻译中…

Problem Statement

翻译中…

There is a set consisting of $N$ distinct integers. The $i$-th smallest element in this set is $S_i$. We want to divide this set into two sets, $X$ and $Y$, such that:

翻译中…
  • The absolute difference of any two distinct elements in $X$ is $A$ or greater.
  • The absolute difference of any two distinct elements in $Y$ is $B$ or greater.
翻译中…

How many ways are there to perform such division, modulo $10^9 + 7$? Note that one of $X$ and $Y$ may be empty.

翻译中…

Constraints

翻译中…
  • All input values are integers.
  • $1 ≦ N ≦ 10^5$
  • $1 ≦ A , B ≦ 10^{18}$
  • $0 ≦ S_i ≦ 10^{18}(1 ≦ i ≦ N)$
  • $S_i < S_{i+1}(1 ≦ i ≦ N - 1)$
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

N A B
S_1
:
S_N

翻译中…

Output

翻译中…

Print the number of the different divisions under the conditions, modulo $10^9 + 7$.

翻译中…

样例

Input #1
5 3 7
1
3
6
9
12
Output #1
5
There are five ways to perform division: - $X=${$1,6,9,12$}, $Y=${$3$} - $X=${$1,6,9$}, $Y=${$3,12$} - $X=${$3,6,9,12$}, $Y=${$1$} - $X=${$3,6,9$}, $Y=${$1,12$} - $X=${$3,6,12$}, $Y=${$1,9$}
Input #2
7 5 3
0
2
4
7
8
11
15
Output #2
4
Input #3
8 2 9
3
4
5
13
15
22
26
32
Output #3
13
Input #4
3 3 4
5
6
7
Output #4
0
题目信息
题号
agc009_c
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。