题目描述
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 \ge 0$），之后结束一轮操作。
如果 Madeline 在任意时刻经过了某个草莓，则视为获得该草莓，问期望获得的草莓个数。为了方便，所有运算在 $\text{mod} , P = 1004535809 = 479 \times 2^{21} + 1$ 意义下进行。
输入格式
第一行输入三个整数 $n, p, q$。
接下来 $n$ 行，第 $i$ 行两个整数 $u_i, v_i$。
输出格式
输出一行一个整数表示答案。
样例
样例输入 1
3 502267905 502267905 1 0 1 2 2 2
样例输出 1
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 \le n \le 5000, 0 \le u_i, v_i \le 10^7, |u_i - v_i| \le 5000, 0 \le p, q < P, p \ne 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 \le$ | 特殊性质 | 分数 |
|---|---|---|---|
| $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 \le 1$ | $10$ |
| $8$ | $5 \times 10^5$ | 无 | $10$ |
| $9$ | $5 \times 10^6$ | $n \le 3000$ | $25$ |
| $10$ | $10^7$ | 无 | $15$ |