P13873 [蓝桥杯 2024 省 Java/Python A] 智力测试

小蓝考上了世界上最好的魔法师学校，然而入学第一件事就是智力测试，老师给出了一个 $n \times m$ 大小的棋盘，同时对每行每列设置了权重 $\{R_1, R_2, \cdots, R_n\}$ 和 $\{C_1, C_2, \cdots, C_m\}$，因此，对于第 $r$ 行第 $c$ 列的格子 $(r, c)$，其权重为一个二元组 $(R_r, C_c)$。 小蓝可以在格子之间进行移动，若某时刻小蓝在格子 $(r, c)$，那么他可以一步走到任意的格子 $(r', c)$ 或 $(r, c')$，其中 $r', c'$ 满足： （1）$R_{r'} > R_r, C_{c'} > C_c$， （2）$\nexists r''. R_{r'} > R_{r''} > R_r; \nexists c''. C_{c'} > C_{c''} > C_r$。 之后，老师提出了 $T$ 个问题，第 $i$ 个问题为：假设小蓝从格子 $(s_r^i, s_c^i)$ 出发，移动到格子 $(t_r^i, t_c^i)$ 有多少种不同的走法，答案对 $1000000007$ 取模。

输入的第一行包含三个正整数 $n, m, T$，相邻整数之间使用一个空格分隔。 第二行包含 $n$ 个正整数 $R_1, R_2, \cdots, R_n$，相邻整数之间使用一个空格分隔。 第三行包含 $m$ 个正整数 $C_1, C_2, \cdots, C_m$，相邻整数之间使用一个空格分隔。 接下来 $T$ 行，第 $i$ 行包含四个正整数 $s_r^i, s_c^i, t_r^i, t_c^i$，相邻整数之间使用一个空格分隔。

输出 $T$ 行，每行包含一个整数，依次表示每个问题的答案。

**【样例说明】** 询问 1： - $(4, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (1, 4) \rightarrow (1, 1)$; - $(4, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 1) \rightarrow (1, 1)$; - $(4, 4) \rightarrow (2, 4) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (1, 1)$; - $(4, 4) \rightarrow (4, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (1, 1)$。 询问 2： - 不存在方案可以从 $(2, 2)$ 走到 $(2, 4)$。 **【评测用例规模与约定】** 对于 $20\%$ 的评测用例，$1 \leq n, m, T \leq 10^3$； 对于所有评测用例，$1 \leq n, m, T \leq 10^5$，$1 \leq R_i, C_i \leq 10^8$，$1 \leq s_r^i, t_r^i \leq n$，$1 \leq s_c^i, t_c^i \leq m$。