[AdditionalFile5566.zip](file://AdditionalFile5566.zip?type=additional_file)

#5566. 「ROIR 2026 Day1」棋子摆放

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 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

输入

1 4
4 4

输出

17

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

样例 2

输入

2 2
1 2
2 1

输出

10

样例 3

输入

3 5
2 5
3 4
4 4

输出

4480

数据范围与提示

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