D - Colorful Balls Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 10001000 点

問題文

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

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

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

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

制約

  • 1≦N≦2×1051 ≦ N ≦ 2 × 10^5
  • 1≦X,Y≦1091 ≦ X, Y ≦ 10^9
  • 1≦ci≦N1 ≦ c_i ≦ N
  • 1≦wi≦1091 ≦ w_i ≦ 10^9
  • X,Y,ci,wiX,Y,c_i, w_i はいずれも整数

入力

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

NN XX YY
c1c_1 w1w_1
::
cNc_N wNw_N

出力

答えを出力せよ。

入力例 1Copy

Copy
4 7 3
3 2
4 3
2 1
4 4

出力例 1Copy

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

入力例 2Copy

Copy
1 1 1
1 1

出力例 2Copy

Copy
1

入力例 3Copy

Copy
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

出力例 3Copy

Copy
129729600

Score : 10001000 points

Problem Statement

Snuke arranged NN colorful balls in a row. The ii-th ball from the left has color cic_i and weight wiw_i.

He can rearrange the balls by performing the following two operations any number of times, in any order:

  • Operation 11: Select two balls with the same color. If the total weight of these balls is at most XX, swap the positions of these balls.
  • Operation 22: Select two balls with different colors. If the total weight of these balls is at most YY, swap the positions of these balls.

How many different sequences of colors of balls can be obtained? Find the count modulo 109+710^9 + 7.

Constraints

  • 1≤N≤2×1051 ≤ N ≤ 2 × 10^5
  • 1≤X,Y≤1091 ≤ X, Y ≤ 10^9
  • 1≤ci≤N1 ≤ c_i ≤ N
  • 1≤wi≤1091 ≤ w_i ≤ 10^9
  • X,Y,ci,wiX, Y, c_i, w_i are all integers.

Input

Input is given from Standard Input in the following format:

NN XX YY
c1c_1 w1w_1
::
cNc_N wNw_N

Output

Print the answer.

Sample Input 1Copy

Copy
4 7 3
3 2
4 3
2 1
4 4

Sample Output 1Copy

Copy
2
  • The sequence of colors (2,4,3,4)(2,4,3,4) can be obtained by swapping the positions of the first and third balls by operation 22.
  • It is also possible to swap the positions of the second and fourth balls by operation 11, but it does not affect the sequence of colors.

Sample Input 2Copy

Copy
1 1 1
1 1

Sample Output 2Copy

Copy
1

Sample Input 3Copy

Copy
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

Sample Output 3Copy

Copy
129729600

2025-04-06 (Sun)
03:50:27 +00:00