【MX-X1-T2】「KDOI-05」简单的有限网格问题

小 S 在玩一款小游戏。游戏中会有一个 $n\times m$ 的棋盘，其中 $k$ 个位置上有星星。初始有一个捕捉器，在 $(x,y)$ 位置。每次操作，你可以将捕捉器移动到同行或同列的某个位置，使得新位置与原位置不同且必须保证新位置 $(x',y')$ 满足 $1\leq x'\leq n$，$1\leq y'\leq m$。**捕捉器会捕捉 $(x,y)$ 到 $(x',y')$ 路径上所有的星星**。一个星星被捕捉后将会消失。 游戏的目标是在恰好两步内获得尽可能多的星星，然而小 S 不会玩，于是每次就会随意挑选一个可以移动到的新位置进行移动。对于 $(n+m-2)^2$ 种小 S 的不同移动方案，求捕捉到的星星数量之和，答案对 $10^9+7$ 取模。

第一行三个正整数 $n,m,k$，表示棋盘大小与星星个数。 第二行两个正整数 $x,y$，表示捕捉器初始位置。 接下来 $k$ 行，每行两个正整数，表示每颗星星所在的位置 $(p,q)$。每个位置上可以有多颗星星。

一行，一个非负整数，表示对于 $(n+m-2)^2$ 种小 S 的不同移动方案，他能捕捉到的星星数量之和，对 $10^9+7$ 取模。

3 3 4
2 2
1 1
1 2
1 3
3 1

11

5 8 9
2 7
1 7
2 2
4 7
4 5
4 7
2 8
5 2
1 7
1 7

153

**【样例解释 \#1】** 网格图中，一种合法的移动捕捉器的方案是： $$(2,2)\to(1,2)\to(1,3)$$ 在该方案中，可以捕捉到位置在 $(1,2)$ 和 $(1,3)$ 的各 $1$ 颗星星。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n\leq$ | $m\leq$ | |:--:|:--:|:--:|:--:| | $1$ | $5$ | $50$ | $50$ | | $2$ | $10$ | $1000$ | $1000$ | | $3$ | $20$ | $10^5$ | $10^5$ | | $4$ | $25$ | $10^5$ | $10^9$ | | $5$ | $25$ | $10^9$ | $10^9$ | | $6$ | $15$ | $10^{18}$ | $10^{18}$ | 对于 $100\%$ 的数据，$1\leq k\leq10^5$，$1\leq n,m\leq10^{18}$，$1\leq x,p\leq n$，$1\leq y,q\leq m$，$(x,y)\neq(p,q)$。