题目描述

すぬけくんは $N$ 個の色が塗られたボールを一列に並べました。 左から $i$ 番目のボールは色 $c_i$ で塗られていて、その重さは $w_i$ です。

すぬけくんは以下の $2$ 種類の操作を任意の順序で何回でも繰り返してボールの配置を変更することができます。

• 操作 $1$：色が同じであるような $2$ つのボールを選ぶ。$2$ つのボールの重さの和が $X$ 以下なら、$2$ つのボールの位置を入れ替える。
• 操作 $2$：色が異なるような $2$ つのボールを選ぶ。$2$ つのボールの重さの和が $Y$ 以下なら、$2$ つのボールの位置を入れ替える。

最終的なボールの色の並びとしてありうるような数列の数を modulo $10^9\ +\ 7$ で求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

$N$ 个球排成一排，第 $i$ 个球的颜色为 $c_i$，重量为 $w_i$。我们定义「一次操作」为：选择两个颜色相同，且重量之和不超过 $X$ 的球，交换它们的位置；或选择两个颜色不同，且重量之和不超过 $Y$ 的球，交换它们的位置。问进行任意次操作后，可以得到多少种不同的颜色序列。输出答案对 $10^9+7$ 取模的结果。

4 7 3
3 2
4 3
2 1
4 4

2

1 1 1
1 1

1

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\ ≦\ N\ ≦\ 2\ ×\ 10^5$
• $1\ ≦\ X,\ Y\ ≦\ 10^9$
• $1\ ≦\ c_i\ ≦\ N$
• $1\ ≦\ w_i\ ≦\ 10^9$
• $X,Y,c_i,\ w_i$ はいずれも整数

Sample Explanation 1

- 操作 $2$ により左から $1$ 番目のボールの位置と左から $3$ 番目のボールの位置を入れ替えることで、$(2,4,3,4)$ という色の並びを作ることが可能です。 - 操作 $1$ により左から $2$ 番目のボールの位置と左から $4$ 番目のボールの位置を入れ替えることも可能ですが、色の並びは変化しません。