给定一个大小为 $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 \le 2 \cdot 10^5$, $1 \le m \le 10^9$）。
接下来 $n$ 行，每行包含两个整数 $r_i$ 和 $c_i$（$1 \le r_i, c_i \le m$）。
输出格式
输出一个整数 —— 满足条件的放置方案数量，对 $10^9 + 7$ 取模。
子任务
| 子任务 | 分值 | 额外限制 | 依赖子任务 |
|---|---|---|---|
| 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 |
样例数据
输入
1 4 4 4
输出
17
输入
2 2 1 2 2 1
输出
10
输入
3 5 2 5 3 4 4 4
输出
4480
说明
在第一个样例中，整个棋盘上最多只能放置一个棋子。共有 $4 \times 4 = 16$ 种放置一个棋子的方案，以及 $1$ 种不放置任何棋子的方案。