AT_agc009_c [AGC009C] Division into Two

题目描述

有一个包含 $N$ 个互不相同整数的集合。该集合中第 $i$ 小的元素为 $S_i$。现在要将这个集合划分为 $X$ 和 $Y$ 两个集合，使得：

• 属于 $X$ 的任意两个不同元素，其差的绝对值不少于 $A$；
• 属于 $Y$ 的任意两个不同元素，其差的绝对值不少于 $B$。

请计算满足上述条件的划分方法数，并对 $10^9+7$ 取模输出。注意，允许 $X$ 或 $Y$ 为空集。

输入格式

输入以如下格式从标准输入读入：

$N$ $A$ $B$ $S_1$ $S_2$ $\ldots$ $S_N$

输出格式

输出满足条件的划分方法数，对 $10^9+7$ 取模。

样例 1

输入

5 3 7
1
3
6
9
12

输出

5

样例 2

输入

7 5 3
0
2
4
7
8
11
15

输出

4

样例 3

输入

8 2 9
3
4
5
13
15
22
26
32

输出

13

样例 4

输入

3 3 4
5
6
7

输出

0

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq A, B \leq 10^{18}$
• $0 \leq S_i \leq 10^{18}\ (1 \leq i \leq N)$
• $S_i < S_{i+1}\ (1 \leq i \leq N-1)$

样例解释 1

有如下 $5$ 种划分方法：

• $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\}$

由 ChatGPT 4.1 翻译