P12512 [集训队互测 2024] 冲刺

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$。

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

### 样例解释 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$ | 无 | $5$ | | 3 | $10^7$ | $p = 0$ | $5$ | | 4 | $10^7$ | $q = 0$ | $5$ | | 5 | $5 \times 10^5$ | $b = 0$ | $5$ | | 6 | $10^7$ | $b = 0$ | $15$ | | 7 | $10^7$ | $b \leq 1$ | $10$ | | 8 | $5 \times 10^5$ | 无 | $10$ | | 9 | $5 \times 10^6$ | $n \leq 3000$ | $25$ | | 10 | $10^7$ | 无 | $15$ |