AT_agc012_d [AGC012D] Colorful Balls

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