题目描述

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