P15129 [ROIR 2026] 筹码放置

给定一个大小为 $m \times m$ 的方形棋盘。棋盘的行和列从 $1$ 到 $m$ 编号。 需要在棋盘上放置筹码，使得每个格子内最多有一个筹码。同时，必须满足 $n$ 条限制。第 $i$ 条限制给出两个整数 $r_i$ 和 $c_i$，这意味着在坐标为 $[1 \ldots r_i] \times [1 \ldots c_i]$ 的矩形区域内，最多只能放置一个筹码。 要求计算满足所有限制的不同筹码放置方案的数量，并对 $10^9+7$ 取模后的余数。

输入数据的第一行包含两个整数 $n$ 和 $m$ —— 限制的数量和棋盘的尺寸（$1 \le n \leq 2 \cdot 10^5$，$1 \leq m \le 10^9$）。 接下来 $n$ 行，每行包含两个数字 $r_i$ 和 $c_i$（$1 \le r_i, c_i \le m$）。

输出一个数字 —— 允许的筹码放置方案数对 $10^9+7$ 取模的结果。

### 样例解释 在第一个样例中，整个棋盘上最多只能放置一个筹码。有 $4 \times 4 = 16$ 种放置一个筹码的方案，以及 $1$ 种不放置任何筹码的方案。 ### 评分规则 | 子任务 | 分值 | 额外限制 | 必要子任务 | |:-:|:-:|:-:|:-:| | 1 | 3 | $n \le 10, m \le 4$ | --- | | 2 | 6 | $n = 1, m \le 1000$ | --- | | 3 | 8 | $n \le 10, m \le 1000$ | 1, 2 | | 4 | 8 | $n \le 15, m \le 10^9$ | 1–3 | | 5 | 10 | $n \le 2500, m \le 100$ | 1 | | 6 | 10 | $n \le 2500, m \le 250$ | 1, 5 | | 7 | 10 | $n \le 2500, m \le 1000$ | 1–3, 5, 6 | | 8 | 10 | $n \le 2500, m \le 10^5$ | 1–3, 5–7 | | 9 | 15 | $n \le 2 \cdot 10^5, m \le 2 \cdot 10^5$ | 1–3, 5–8 | | 10 | 20 | 无额外限制 | 1–9 | 翻译由 DeepSeek 完成