题意：给定 $n,m$ 和平面上的 $k$ 个点，数有多少个矩形（左下 $(x_1,y_1)$、右上 $(x_2,y_2)$，要求 $1\le x_1\le x_2\le n$、$1\le y_1\le y_2\le m$）里至少含一个给定点，答案对 $10^9+7$ 取模。

最直白的做法是把所有矩形都枚举一遍。先按输入把点打到一张二维前缀和表上，这样判断「某个矩形里有没有点」就是 $O(1)$ 的；然后四重循环枚举 $x_1\le x_2$ 与 $y_1\le y_2$，有就累加。

代价是 $\Theta(n^2m^2)$，可以过测试点 $1,2$，20 分。

直接数「至少包含一个给定点的矩形」不好数，改成按 x 方向分列枚举。

把 $k$ 个点的 $x$ 坐标去重排序，得到若干列 $v_1<v_2<\dots<v_t$（再加两个哨兵 $v_0=0$、$v_{t+1}=n+1$）。矩形的左边界 $x_1$ 落在哪两条相邻列之间、右边界 $x_2$ 落在哪两条之间，一共只有 $O(t^2)$ 种「列区间」可以枚举。

固定一段列区间（矩形至少要横跨第 $i$ 到第 $j$ 列里的点）之后再看 y 方向：

• 左边界 $x_1$ 只能在 $(v_{i-1},v_i]$ 里取，共 $v_i-v_{i-1}$ 种；
• 右边界 $x_2$ 只能在 $[v_j,v_{j+1})$ 里取，共 $v_{j+1}-v_j$ 种；
• 中间这些列的点，按 $y$ 从小到大依次插入有序集合。插入一个点 $y$ 时设它在已插入集合里的前驱、后继分别是 $b,t$，那么以这个点为最低点、且 y 区间内至少含一个点的 $(y_1,y_2)$ 对数正好是 $(t-y)(y-b)$。

把所有点这样累加起来，每一对合法的 $(y_1,y_2)$ 都会被「它包含的最低那个点」统计恰好一次，不重不漏。于是这段列区间的贡献就是

$$(\text{y 方向的合法区间数})\times(v_i-v_{i-1})\times(v_{j+1}-v_j)$$

对所有列区间求和即可。

列数不超过 $k+1$，每段列区间的 y 方向扫描用有序集合做，总复杂度 $O(k^2\log k)$。