不幸的是,任务的正式描述太长了,所以这里是图例。
研究漫游车终于到达火星表面并准备完成其任务。不幸的是,由于导航系统设计的错误,流动站位于错误的位置。
流动站将在由 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)