U361837 【MAROI csp七连Day1】D.Basketball

现在有一个 $n$ 行 $m$ 列的矩阵，你需要求出从 $(x1,y1)$ 走到 $(x2,y2)$ 的方案数（只能往右方和下方走），但是需要注意的是，矩阵中间可能会有一处炸弹，你不能走到那个地方，否则炸弹就会爆炸。

输入共 $q+1$ 行： 第 $1$ 行输入 $n,m,q,opt$，分别表示矩阵的大小及询问的次数，若 $opt=1$，则需要额外输入一个含有炸弹的坐标。 之后 $q$ 行输入 $x1,y1,x2,y2$，表示从 $x1,y1$ 走到 $x2,y2$ 的方案数。

对于每组询问，给出能从 $x1,y1$ 走到 $x2,y2$ 的方案数，由于结果可能很大，所以需要你对 $10^9+7$ 取模。

**【样例 \#3】** 见附件中的 `D3.in` 与 `D3.out`。 **【样例 \#4】** 见附件中的 `D4.in` 与 `D4.out`。 **【数据范围】** 数据保证 $x1,y1,x2,y2$ 均为合法的。 | 测试点编号 | $n,m \le$ | $q \le$ | $opt=$ | 特殊条件 | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $10$ | $10$ | $0$ | 无 | | $3 \sim 4$ | $10$ | $10$ | $1$ | 无 | | $5$ | $10^3$ | $10^2$ | $0$ | 无 | | $6$ | $10^3$ | $10^2$ | $1$ | 无 | | $7$ | $10^3$ | $10^3$ | $0,1$ | 无 | | $8 \sim 10$ | $10^4$ | $10^3$ | $0,1$ | 无 | | $11 \sim 12$ | $10^4$ | $10^4$ | $0,1$ | 无 | | $13 \sim 16$ | $10^4 \times 5$ | $10^4 \times 5$ | $0,1$ | 无 | | $17 \sim 18$ | $10^5$ | $10^5$ | $0,1$ | 无 | | $19$ | $10^6$ | $10^6$ | $0,1$ | 保证数据在范围内均匀生成 | | $20$ | $2 \times 10^6$ | $2 \times 10^6$ | $0,1$ | 无 |