Дана квадратная доска размера $$$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$$$.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 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 44 4
17
2 21 22 1
10
3 52 53 44 4
4480
В первом примере на всей доске может быть поставлено не более одной фишки. Есть $$$4 \times 4 = 16$$$ вариантов поставить одну фишку и $$$1$$$ вариант с нулём расставленных фишек.
