研究探测车

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

研究探测车将在一个 $n$ 行 $m$ 列的网格上运行，格子坐标记为 $(r,c)$。探测车当前位于 $(1,1)$，需要到达 $(n,m)$。

探测车会等概率随机选择一条从起点到终点的最短路径。最短路径上的每一步只能向下或向右移动。

探测车的初始电量为 $s$。网格中有 $k$ 个异常格；每当探测车进入异常格时，若进入前电量为 $x$，则离开该格时电量变为

若起点 $(1,1)$ 或终点 $(n,m)$ 是异常格，也会产生上述影响。

请计算探测车到达终点后的电量期望。

输入格式

第一行包含四个整数 $n,m,k,s$，分别表示网格行数、列数、异常格数量和初始电量。

接下来 $k$ 行，每行包含两个整数 $r_i,c_i$，表示一个异常格。保证所有异常格互不相同。

输出格式

答案总能表示为最简分数 $P/Q$。输出

其中 $Q^{-1}$ 表示 $Q$ 在模 $10^9+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\le n,m\le100000$，$0\le k\le2000$，$1\le s\le1000000$，且 $1\le r_i\le n$、$1\le c_i\le m$。

说明

第一组样例共有六条最短路径，对应终点电量依次为 $6,6,11,3,6,6$，所以期望为 $19/3$。