English · Original
Chinese · Translation
Formal · Original
_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.
## Input
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.
## Output
The answer can always be represented as an irreducible fraction . Print the only integer _P_·_Q_ - 1 modulo 109 + 7.
[samples]
## Note
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)
_不幸的是，任务的正式描述过于冗长，因此这里给出传说版本。_
研究漫游车终于抵达火星表面，准备完成其任务。然而，由于导航系统设计错误，漫游车位于错误的位置。
漫游车将在一个由 #cf_span[n] 行和 #cf_span[m] 列组成的网格上运行。我们定义 #cf_span[(r, c)] 为位于第 #cf_span[r] 行和第 #cf_span[c] 列的单元格。从每个单元格，漫游车可以移动到与当前单元格共享一条边的任意单元格。
漫游车当前位于单元格 #cf_span[(1, 1)]，需要移动到单元格 #cf_span[(n, m)]。它将随机选择一条从起点到终点的*最短路径*，每条可能路径被选中的概率相等。
漫游车的货舱中包含进行研究所需的电池。初始时，电池电量为 #cf_span[s] 单位能量。
某些单元格包含异常。每当漫游车到达一个包含异常的单元格时，电池电量会减少一半并向下取整。形式上，若漫游车到达异常单元格前电量为 #cf_span[x]，则电量将变为 。
在漫游车随机选择一条最短路径前进的过程中，请计算其到达单元格 #cf_span[(n, m)] 时电池电量的期望值。如果单元格 #cf_span[(1, 1)] 和 #cf_span[(n, m)] 包含异常，它们也会对电池电量产生影响。
输入的第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[k] 和 #cf_span[s]（#cf_span[1 ≤ n, m ≤ 100 000]，#cf_span[0 ≤ k ≤ 2000]，#cf_span[1 ≤ s ≤ 1 000 000]）——分别表示网格的行数、列数、包含异常的单元格数量以及电池的初始电量。
接下来的 #cf_span[k] 行，每行包含两个整数 #cf_span[ri] 和 #cf_span[ci]（#cf_span[1 ≤ ri ≤ n]，#cf_span[1 ≤ ci ≤ m]）——表示包含异常的单元格坐标。保证每个单元格在该列表中最多出现一次。
答案总可以表示为一个最简分数 。请输出仅一个整数 #cf_span[P·Q - 1] 对 #cf_span[10^9 + 7] 取模的结果。
在第一个样例中，漫游车从以下六条路径中随机选择一条：
电池电量的期望值由以下公式计算：
。
因此 #cf_span[P = 19]，且 #cf_span[Q = 3]。
#cf_span[3 - 1] 对 #cf_span[10^9 + 7] 取模等于 #cf_span[333333336]。
#cf_span[19·333333336 = 333333342 (mod 10^9 + 7)]
## Input
输入的第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[k] 和 #cf_span[s]（#cf_span[1 ≤ n, m ≤ 100 000]，#cf_span[0 ≤ k ≤ 2000]，#cf_span[1 ≤ s ≤ 1 000 000]）——分别表示网格的行数、列数、包含异常的单元格数量以及电池的初始电量。接下来的 #cf_span[k] 行，每行包含两个整数 #cf_span[ri] 和 #cf_span[ci]（#cf_span[1 ≤ ri ≤ n]，#cf_span[1 ≤ ci ≤ m]）——表示包含异常的单元格坐标。保证每个单元格在该列表中最多出现一次。
## Output
答案总可以表示为一个最简分数 。请输出仅一个整数 #cf_span[P·Q - 1] 对 #cf_span[10^9 + 7] 取模的结果。
[samples]
## Note
在第一个样例中，漫游车从以下六条路径中随机选择一条： ，经过单元格 #cf_span[(2, 3)] 后电量变为 #cf_span[6]。 ，经过单元格 #cf_span[(2, 3)] 后电量变为 #cf_span[6]。 ，电量保持不变，仍为 #cf_span[11]。 ，经过单元格 #cf_span[(2, 1)] 和 #cf_span[(2, 3)] 后电量依次变为 #cf_span[6] 和 #cf_span[3]。 ，经过单元格 #cf_span[(2, 1)] 后电量变为 #cf_span[6]。 ，经过单元格 #cf_span[(2, 1)] 后电量变为 #cf_span[6]。电池电量的期望值由以下公式计算： 。因此 #cf_span[P = 19]，且 #cf_span[Q = 3]。#cf_span[3 - 1] 对 #cf_span[10^9 + 7] 取模等于 #cf_span[333333336]。#cf_span[19·333333336 = 333333342 (mod 10^9 + 7)]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the grid.
Let $ s \in \mathbb{Z}^+ $ be the initial battery charge.
Let $ k \in \mathbb{Z}_{\geq 0} $ be the number of anomaly cells.
Let $ A = \{(r_i, c_i) \in [n] \times [m] \mid i \in [k]\} $ be the set of anomaly cell coordinates.
A shortest path from $ (1,1) $ to $ (n,m) $ consists of exactly $ d = n + m - 2 $ steps: $ n-1 $ down and $ m-1 $ right, in some order.
The total number of such paths is $ \binom{n+m-2}{n-1} $.
Each path visits $ n + m - 1 $ cells, including start $ (1,1) $ and end $ (n,m) $.
Let $ X $ be the random variable denoting the final battery charge after traversing a uniformly random shortest path.
The battery charge evolves as follows:
- Start with charge $ s $.
- For each cell $ (r,c) $ on the path that belongs to $ A $, the charge is updated as $ x \mapsto \left\lfloor \frac{x}{2} \right\rfloor $.
Let $ Y $ be the number of anomaly cells visited along the random path.
**Constraints**
1. $ 1 \leq n, m \leq 100{,}000 $
2. $ 0 \leq k \leq 2000 $
3. $ 1 \leq s \leq 1{,}000{,}000 $
4. All anomaly coordinates are distinct and lie within $ [n] \times [m] $.
**Objective**
Compute the expected value of the final battery charge:
$$
\mathbb{E}[X] = \sum_{p \in \mathcal{P}} \frac{1}{\binom{n+m-2}{n-1}} \cdot f(p)
$$
where $ \mathcal{P} $ is the set of all shortest paths from $ (1,1) $ to $ (n,m) $, and $ f(p) $ is the final charge after applying $ \left\lfloor \cdot / 2 \right\rfloor $ for each anomaly cell on path $ p $.
Equivalently, define for each subset $ S \subseteq A $, let $ N_S $ be the number of shortest paths that include exactly the anomaly cells in $ S $ (and no others). Then:
$$
\mathbb{E}[X] = \frac{1}{\binom{n+m-2}{n-1}} \sum_{S \subseteq A} N_S \cdot g(S)
$$
where $ g(S) $ is the result of applying $ \left\lfloor \cdot / 2 \right\rfloor $ exactly $ |S| $ times to $ s $, in any order (since floor division by 2 is deterministic and order-independent).
Let $ h(t) = \left\lfloor \frac{ \left\lfloor \frac{ \cdots \left\lfloor \frac{s}{2} \right\rfloor \cdots }{2} \right\rfloor }{2} \right\rfloor $ ($ t $ times). Then:
$$
\mathbb{E}[X] = \sum_{t=0}^{k} h(t) \cdot \mathbb{P}(\text{exactly } t \text{ anomalies visited})
$$
Let $ p_t = \mathbb{P}(\text{exactly } t \text{ anomalies on a random shortest path}) $. Then:
$$
\mathbb{E}[X] = \sum_{t=0}^{k} h(t) \cdot p_t
$$
We must compute this expectation as an irreducible fraction $ \frac{P}{Q} $, and output $ P \cdot Q^{-1} \mod (10^9 + 7) $.
API Response (JSON)
{
"problem": {
"name": "E. Research Rover",
"description": {
"content": "_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. Unfortun",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF722E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_Unfortunately, the formal description of the task turned out to be too long, so here is the legend._\n\nResearch rover finally reached the surface of Mars and is ready to complete its mission. Unfortun...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_不幸的是，任务的正式描述过于冗长，因此这里给出传说版本。_\n\n研究漫游车终于抵达火星表面，准备完成其任务。然而，由于导航系统设计错误，漫游车位于错误的位置。\n\n漫游车将在一个由 #cf_span[n] 行和 #cf_span[m] 列组成的网格上运行。我们定义 #cf_span[(r, c)] 为位于第 #cf_span[r] 行和第 #cf_span[c] 列的单元格。从每个单元格，漫游车可以...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the grid. \nLet $ s \\in \\mathbb{Z}^+ $ be the initial battery charge. \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the number of anomaly ...",
"is_translate": false,
"language": "Formal"
}
]
}