← 返回题目列表

AtCoder · agc012_d

D. 七彩球

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

潜伏安排 N 彩色球连续。 的 i左边第一个球有颜色 c_i 和重量 w_i.

他可以通过以任意顺序执行任意次数的以下两个操作来重新排列球:

  • 操作 1:选择两个颜色相同的球。如果这些球的总重量最多为 X,交换这些球的位置。
  • 操作 2:选择两个不同颜色的球。如果这些球的总重量最多为 Y,交换这些球的位置。

可以获得多少种不同颜色的球序列?求计数模数 10^9 + 7.

约束

  • 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 均为整数。

输入

输入由标准输入按以下格式给出:

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,4,3,4) 通过运算交换第一个和第三个球的位置即可得到 2.
  • 也可以通过操作交换第二个和第四个球的位置 1,但不影响颜色顺序。

示例输入 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