题目描述

すぬけくん将 $N$ 个涂有颜色的小球排成一列。第 $i$ 个小球从左往右依次编号，颜色为 $c_i$，重量为 $w_i$。

すぬけくん可以按任意顺序无限次重复以下两种操作，对小球的排列进行调整：

• 操作 $1$：任选两个颜色相同的小球，如果这两个小球的重量和不超过 $X$，则可以交换它们的位置。
• 操作 $2$：任选两个颜色不同的小球，如果这两个小球的重量和不超过 $Y$，则可以交换它们的位置。

请你计算所有最终可能出现的颜色排列的方案数。答案对 $10^9 + 7$ 取模。

输入格式

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

$N$ $X$ $Y$ $c_1$ $w_1$ $: \cdots :$ $c_N$ $w_N$

输出格式

请输出最终可能得到的颜色排列方案数。

样例 1

输入

4 7 3
3 2
4 3
2 1
4 4

输出

2

样例 2

输入

1 1 1
1 1

输出

1

样例 3

输入

21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15

输出

129729600

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq X, Y \leq 10^9$
• $1 \leq c_i \leq N$
• $1 \leq w_i \leq 10^9$
• $X, Y, c_i, w_i$ 均为整数

样例解释 1

• 通过操作 $2$ 可以交换第 $1$ 个和第 $3$ 个小球的位置，因此可以得到颜色排列 $(2,4,3,4)$。
• 通过操作 $1$ 也可以交换第 $2$ 个和第 $4$ 个小球的位置，但颜色排列没有发生变化。

由 ChatGPT 5 翻译