P15129 [ROIR 2026] Chip Placement

You are given a square board of size $m \times m$. The rows and columns of the board are numbered from $1$ to $m$. You need to place chips on the board so that each cell contains at most one chip. At the same time, you must satisfy $n$ constraints. The $i$-th constraint gives two integers $r_i$ and $c_i$, meaning that in the rectangular area with coordinates $[1 \ldots r_i] \times [1 \ldots c_i]$, at most one chip can be placed. Compute the number of different chip placement schemes that satisfy all constraints, and output the result modulo $10^9+7$.

The first line of the input contains two integers $n$ and $m$ — the number of constraints and the size of the board ($1 \le n \leq 2 \cdot 10^5$, $1 \leq m \le 10^9$). The next $n$ lines each contain two numbers $r_i$ and $c_i$ ($1 \le r_i, c_i \le m$).

Output one number — the number of valid chip placement schemes modulo $10^9+7$.

### Sample Explanation In the first sample, at most one chip can be placed on the entire board. There are $4 \times 4 = 16$ ways to place one chip, and $1$ way to place no chips. ### Scoring Rules | Subtask | Points | Additional Constraints | Required Subtasks | |:-:|:-:|:-:|:-:| | 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 | No additional constraints | 1–9 | Translated by DeepSeek. Translated by ChatGPT 5