分数: 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