← 返回题目列表

Codeforces · 722/E

E. 研究漫游车

中文机器翻译题面 查看原题

不幸的是,任务的正式描述太长了,所以这里是图例。

研究漫游车终于到达火星表面并准备完成其任务。不幸的是,由于导航系统设计的错误,流动站位于错误的位置。

流动站将在由 n 行和 m 列组成的网格上运行。我们将位于 r 行 c 列的单元格定义为 (r, c)。流动站能够从每个单元移动到与当前单元共享一侧的任何单元。

流动站当前位于小区 (1, 1),必须移动到小区 (n, m)。它将随机遵循这两个单元之间的一些最短路径。每种可能的方式都是等概率地选择的。

流动站的货物部分包含进行研究所需的电池。最初,电池电量等于 s 单位能量。

一些单元格包含异常。每次漫游车到达出现异常情况的电池时,电池就会损失一半的电量(向下舍入)。形式上,如果在流动站到达异常单元格之前电荷等于 x,则电荷将更改为 $$\left\lfloor \frac{x}{2} \right\rfloor$$。

当流动站选择一条随机最短路径继续前进时,计算到达电池 (n, m) 后电池电量的预期值。如果电池(1, 1)和(n, m)存在异常,也会影响电池的充电。

输入

输入的第一行包含四个整数 n、m、k 和 s(1 ≤ n、m ≤ 100 000、0 ≤ k ≤ 2000、1 ≤ s ≤ 1 000 000)——分别为字段的行数和列数、异常电池数和电池的初始电量。

接下来的 k 行包含两个整数 ri 和 ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) - 包含异常的单元格坐标。确保每个单元格在此列表中出现的次数不超过一次。

输出

答案总是可以表示为不可约分数 $$\frac{p}{q}$$。打印唯一的整数 P·Q - 1 模 109 + 7。

示例

输入 #1

3 3 2 11
2 1
2 3

输出 #1

333333342

输入 #2

4 5 3 17
1 2
3 3
4 1

输出 #2

514285727

输入 #3

1 6 2 15
1 1
1 5

输出 #3

4

注意

在第一个示例中,流动站选择以下六条路线之一:

1. $$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)$$,经过单元格(2, 3)后电荷等于6。
2. $$(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)$$,经过单元格 (2, 3) 后电荷等于 6。
3. $$(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(3,2)\rightarrow(3,3)$$,电荷保持不变,等于 11。
4. $$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)$$,经过单元格 (2, 1) 和 (2, 3) 后,电荷等于 6,然后等于 3。
5. $$(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(3,2)\rightarrow(3,3)$$,经过单元格 (2, 1) 后电荷等于 6。
6. $$(1,1)\rightarrow(2,1)\rightarrow(3,1)\rightarrow(3,2)\rightarrow(3,3)$$,经过单元格 (2, 1) 后电荷等于 6。

电池电量的预期值通过以下公式计算:

$${ \frac { 1 } { 6 } } ( 6 + 6 + 1 1 + 3 + 6 + 6 ) = { \frac { 3 8 } { 6 } } = { \frac { 1 9 } { 3 } }$$。

因此 P = 19,Q = 3。

3 - 1 模 109 + 7 等于 333333336。

19·333333336 = 333333342(模 109 + 7)