[AGC012D] Colorful Balls

题意翻译

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

题目描述

[problemUrl]: https://atcoder.jp/contests/agc012/tasks/agc012_d すぬけくんは $ 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 $

输出格式


答えを出力せよ。

输入输出样例

输入样例 #1

4 7 3
3 2
4 3
2 1
4 4

输出样例 #1

2

输入样例 #2

1 1 1
1 1

输出样例 #2

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

输出样例 #3

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 $ 番目のボールの位置を入れ替えることも可能ですが、色の並びは変化しません。