Research Rover
Contest: Intel Code Challenge Elimination Round (Div. 1 + Div. 2, combined)
Difficulty rating: 2900
Tags: combinatorics, dp

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 $$\left\lfloor \frac{x}{2} \right\rfloor$$.

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.

Input format:
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 ri and ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) — coordinates of the cells, containing anomaly. It's guaranteed that each cell appears in this list no more than once.

Output format:
The answer can always be represented as an irreducible fraction $$\frac{p}{q}$$. Print the only integer P·Q - 1 modulo 109 + 7.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

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

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

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

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

Thus P = 19, and Q = 3.

3 - 1 modulo 109 + 7 equals 333333336.

19·333333336 = 333333342 (mod 109 + 7)

Example input:
3 3 2 11
2 1
2 3

Example output:
333333342

Example input:
4 5 3 17
1 2
3 3
4 1

Example output:
514285727

Editorial:
Several auxiliary statements:
1. The number of paths between cells with coordinates (i1, j1) and (i2, j2), for which i1 ≤ i2 and j1 ≤ j2, is equal to $$(j_{2}-j_{1})+(i_{2}-i_{1})\over i_{2}-i_{1}$$.
2. In order to get the answer it is not necessary to find irreducible fraction $$\frac{p}{q}$$. Suppose that we have found some fraction $$\frac{p_{1}}{q_{1}}$$, for which the following is true: P1 = P * g, Q1 = Q * g. Let's calculate the answer for this fraction: P1 * Q1 - 1 ≡ P * g * (Q * g) - 1 ≡ P * g * Q - 1 * g - 1 ≡ P * g * g - 1 * Q - 1 ≡ P * Q (mod 109 + 7).
From the second statement it implies that the answer can be found in the following form: Q is equal to the number of paths between cells (1, 1) and (n, m), and P is equal to the sum of the battery charges in the endpoint among all paths.
The battery charge in the endpoint does not depend on the order of visit of the anomalies, but only on the number of anomalies on the path. Then in order to calculate the required sum it is enough to count the number of paths that pass through the 0, 1, 2 and so on anomalies. Note that since the original battery charge does not exceed 106, and each time you visit the anomaly it is reduced by half, then in all paths, with the number of anomalies greater than or equal to 20, the charge at the endpoint will be equal to 1.
First let's try to solve a simpler problem: count the number of paths that do not pass through the cells with anomalies. Sort all the cells with anomalies in increasing order of the sum of their coordinates. Then, if the path passes through the anomaly with the number i (in sorted order), then the next cell with anomaly on the path can only be the cell with the number greater than i.
We calculate the following dynamic: F(i) - number of paths which start in the anomaly with the number i, end in the cell (n, m) and don't pass through other anomalies.
Let's denote as paths(i1, j1, i2, j2) the following value: $$(j_{2}-j_{1})+(i_{2}-i_{1})\over i_{2}-i_{1}$$ if i1 ≤ i2, j1 ≤ j2 and 0 otherwise. Values of F can be calculated using the following formula: $$$$.
Every path that passes through at least one anomaly different from the i-th, will be subtracted from the total number of paths exactly once - when the j is equal to the number of the last anomaly on this path.
Let's go back to the original problem: denote as G(i, v) the number of paths which start in the anomaly with the number i, end in the cell (n, m) and pass through exactly v anomalies different from i-th.
For v = 0, G(i, 0) = F(i).
For v > 0, values of G can be calculated using the following formula: $$$$.
Every path that passes through at least v + 1 anomalies different from the i-th, will be subtracted from the total number of paths exactly once - when the j is equal to the number of v-th anomaly from the end on this path. It remains only to subtract all paths that contains less than v anomalies (last part of the formula).
For simplicity, you can add an additional anomaly with coordinates (1, 1).
In the end, let's iterate over the number of anomalies (from 0 to 19) on the path. For each number, we can find the value of the battery charge in the endpoint and multiply it by the number of paths calculated above. Also, add one to the sum for each path that visits 20 or more anomalies.
The resulting complexity of the solution is O(n2 log 106).