题目描述

Madeline 在登顶后下山的途中碰到了 Oshiro，他希望 Madeline 能帮他收集藏在旅馆高处的草莓。

为了方便，我们忽略旅馆的宽度，将其描述为一个 $10^9 \times 10^9$ 的平面。Madeline 初始位于 $(0, 0)$，有 $n$ 个草莓，第 $i$ 个草莓位于 $(u_i, v_i)$。由于旅馆实在太大了，Madeline 决定使用跳跃结合冲刺的办法收集草莓。假设她位于 $(x, y)$，如果 $\min(x, y) < 10^9$，她将会进行如下操作：

• 先以 $q$ 的概率向右跳跃，到达 $(x+1, y)$，或 $1-q$ 的概率向上跳跃，到达 $(x, y+1)$。

然后进入冲刺阶段，一次右上冲刺会使 Madeline 从 $(s, t)$ 直接移动到 $(s+1, t+1)$。她会先进行一次右上冲刺。由于旅馆内有一些能量水晶，她会以 $p$ 的概率再次进入冲刺阶段，或以 $1-p$ 的概率退出。你可以认为 Madeline 在该阶段会以 $(1-p)p^i$ 的概率连续向右上冲刺 $i+1$ 次 ($i \geq 0$)，之后结束一轮操作。

如果 Madeline 在任意时刻经过了某个草莓，则视为获得该草莓，问期望获得的草莓个数。为了方便，所有运算在 $\text{mod}, P = 1004535809 = 479 \times 2^{21} + 1$ 意义下进行。

输入格式

第一行输入三个整数 $n, p, q$。

接下来 $n$ 行，第 $i$ 行两个整数 $u_i, v_i$。

输出格式

输出一行一个整数表示答案。

3 502267905 502267905
1 0
1 2
2 2

753401858

提示

样例解释 1

可以认为 $p = q = \frac{1}{2}$，经过三个点的概率分别为 $\frac{1}{2}, \frac{1}{2}, \frac{1}{4}$。

样例 2 ~ 7

见下发文件，分别满足子任务 1, 3, 4, 5, 7, 9 的限制。

数据范围

对于所有测试点，$1 \leq n \leq 5000$, $0 \leq u_i, v_i \leq 10^7$, $|u_i - v_i| \leq 5000$, $0 \leq p, q < P$, $p \neq 1$。

记 $V = \max \left( \max_{i=1}^{n} u_i, \max_{i=1}^{n} v_i \right)$, $b = \max_{i=1}^{n} |u_i - v_i|$。

子任务编号	$V \leq$	特殊性质	分数
1	$300$	无	$5$
2	$5000$
3	$10^7$	$p = 0$
4		$q = 0$
5	$5 \times 10^5$	$b = 0$
6	$10^7$		$15$
7		$b \leq 1$	$10$
8	$5 \times 10^5$	无
9	$5 \times 10^6$	$n \leq 3000$	$25$
10	$10^7$	无	$15$