题目描述

译自 ROI Regional 2026 Day1 T3. Расстановки фишек

给定一块 $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 \leq n \leq 2 \cdot 10^5,\ 1 \leq m \leq 10^9)$，分别表示限制数量和棋盘大小。

接下来 $n$ 行，每行两个整数 $r_i, c_i$ $(1 \leq r_i, c_i \leq m)$。

输出格式

输出一个整数，表示满足所有限制的合法摆放方案数量，对 $10^9 + 7$ 取模。

1 4
4 4

17

整个棋盘上至多只能放置一个棋子。 有 $4 \times 4 = 16$ 种放置一个棋子的方案，加上 $1$ 种不放置任何棋子的空方案，总计 $17$ 种。

2 2
1 2
2 1

10

3 5
2 5
3 4
4 4

4480

数据范围与提示

详细子任务附加限制及分值如下表所示（只有通过本子任务及所有必要子任务的所有测试，才能获得对应分数）：