#agc009c. [agc009_c]Division into Two

[agc009_c]Division into Two

Problem Statement

There is a set consisting of NN distinct integers. The ii-th smallest element in this set is SiS_i. We want to divide this set into two sets, XX and YY, such that:

  • The absolute difference of any two distinct elements in XX is AA or greater.
  • The absolute difference of any two distinct elements in YY is BB or greater.

How many ways are there to perform such division, modulo 109+710^9 + 7? Note that one of XX and YY may be empty.

Constraints

  • All input values are integers.
  • 1N1051 ≦ N ≦ 10^5
  • 1A,B10181 ≦ A , B ≦ 10^{18}
  • 0Si1018(1iN)0 ≦ S_i ≦ 10^{18}(1 ≦ i ≦ N)
  • Si<Si+1(1iN1)S_i < S_{i+1}(1 ≦ i ≦ N - 1)

Input

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

NN AA BB S1S_1 : SNS_N

Output

Print the number of the different divisions under the conditions, modulo 109+710^9 + 7.


Sample Input 1

5 3 7
1
3
6
9
12

Sample Output 1

5

There are five ways to perform division:

  • X=X={1,6,9,121,6,9,12}, Y=Y={33}
  • X=X={1,6,91,6,9}, Y=Y={3,123,12}
  • X=X={3,6,9,123,6,9,12}, Y=Y={11}
  • X=X={3,6,93,6,9}, Y=Y={1,121,12}
  • X=X={3,6,123,6,12}, Y=Y={1,91,9}

Sample Input 2

7 5 3
0
2
4
7
8
11
15

Sample Output 2

4

Sample Input 3

8 2 9
3
4
5
13
15
22
26
32

Sample Output 3

13

Sample Input 4

3 3 4
5
6
7

Sample Output 4

0