CF722E.Research Rover

Unfortunately, the formal description of the task turned out to be too long, so here is the legend.

Research rover finally reached the surface of Mars and is ready to complete its mission. Unfortunately, due to the mistake in the navigation system design, the rover is located in the wrong place.

The rover will operate on the grid consisting of n rows and m columns. We will define as (r, c) the cell located in the row r and column c. From each cell the rover is able to move to any cell that share a side with the current one.

The rover is currently located at cell (1, 1) and has to move to the cell (n, m). It will randomly follow some shortest path between these two cells. Each possible way is chosen equiprobably.

The cargo section of the rover contains the battery required to conduct the research. Initially, the battery charge is equal to s units of energy.

Some of the cells contain anomaly. Each time the rover gets to the cell with anomaly, the battery looses half of its charge rounded down. Formally, if the charge was equal to x before the rover gets to the cell with anomaly, the charge will change to .

While the rover picks a random shortest path to proceed, compute the expected value of the battery charge after it reaches cell (n, m). If the cells (1, 1) and (n, m) contain anomaly, they also affect the charge of the battery.

不幸的是，该任务的正式描述过长，因此我们给出如下背景故事。

科研探测车终于抵达火星表面，准备执行其使命。然而，由于导航系统设计存在错误，探测车降落在了错误的位置。

探测车将在一个由 $n$ 行和 $m$ 列组成的网格上运行。我们用 $(r,\,c)$ 表示位于第 $r$ 行、第 $c$ 列的格子。从任意格子出发，探测车均可移动至与其共享一条边的任意相邻格子（即上下左右四个方向）。

探测车当前位于格子 $(1,\,1)$，需前往格子 $(n,\,m)$。它将随机选择一条连接这两点的最短路径行进，且所有可能的最短路径被选中的概率相等。

探测车的货舱中装有执行科研任务所需的电池，初始电量为 $s$ 单位能量。

部分格子中存在异常区域。每当探测车进入一个含有异常的格子时，其电池电量将向下取整地减半。形式化地说，若进入异常格子前电量为 $x$，则进入后电量变为
。

在探测车随机选择一条最短路径前往 $(n,\,m)$ 的前提下，请计算其抵达格子 $(n,\,m)$ 后电池电量的期望值。注意：若起点 $(1,\,1)$ 或终点 $(n,\,m)$ 本身含有异常，它们同样会对电量产生影响。

The first line of the input contains four integers n, m, k and s (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 2000, 1 ≤ s ≤ 1 000 000) — the number of rows and columns of the field, the number of cells with anomaly and the initial charge of the battery respectively.

The follow k lines containing two integers r__i and c__i (1 ≤ r__i ≤ n, 1 ≤ c__i ≤ m) — coordinates of the cells, containing anomaly. It's guaranteed that each cell appears in this list no more than once.

输入的第一行包含四个整数 $n$、$m$、$k$ 和 $s$（$1 \leq n, m \leq 100\,000$，$0 \leq k \leq 2000$，$1 \leq s \leq 1\,000\,000$），分别表示场地的行数、列数、存在异常现象的格子数量以及电池的初始电量。

接下来的 $k$ 行，每行包含两个整数 $r_i$ 和 $c_i$（$1 \leq r_i \leq n$，$1 \leq c_i \leq m$），表示存在异常现象的格子的坐标。保证每个格子在此列表中至多出现一次。

The answer can always be represented as an irreducible fraction . Print the only integer P·Q - 1 modulo 109 + 7.

答案总可以表示为一个最简分数 。请输出唯一的整数 $P \cdot Q^{-1} \bmod (10^9 + 7)$。

In the first sample, the rover picks one of the following six routes:

1. , after passing cell (2, 3) charge is equal to 6.
2. , after passing cell (2, 3) charge is equal to 6.
3. , charge remains unchanged and equals 11.
4. , after passing cells (2, 1) and (2, 3) charge equals 6 and then 3.
5. , after passing cell (2, 1) charge is equal to 6.
6. , after passing cell (2, 1) charge is equal to 6.

Expected value of the battery charge is calculated by the following formula:

.

Thus P = 19, and Q = 3.

3 - 1 modulo 109 + 7 equals 333333336.

19·333333336 = 333333342 (mod 109 + 7)

在第一个样例中，探测器选择了以下六条路径之一：

1. ，经过格子 $(2,\,3)$ 后，电量为 $6$。
2. ，经过格子 $(2,\,3)$ 后，电量为 $6$。
3. ，电量保持不变，为 $11$。
4. ，经过格子 $(2,\,1)$ 和 $(2,\,3)$ 后，电量依次变为 $6$ 和 $3$。
5. ，经过格子 $(2,\,1)$ 后，电量为 $6$。
6. ，经过格子 $(2,\,1)$ 后，电量为 $6$。

电池电量的期望值按如下公式计算：

。

因此 $P = 19$，且 $Q = 3$。

$3^{-1} \bmod (10^9 + 7)$ 等于 $333333336$。

$19 \cdot 333333336 = 333333342 \pmod{10^9 + 7}$