Statement is not available in English language
C. Расстановки фишек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана квадратная доска размера $$$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$$$.

Система оценки
ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
13$$$n \le 10, m \le 4$$$—
26$$$n = 1, m \le 1000$$$—
38$$$n \le 10, m \le 1000$$$1, 2
48$$$n \le 15, m \le 10^9$$$1–3
510$$$n \le 2500, m \le 100$$$1
610$$$n \le 2500, m \le 250$$$1, 5
710$$$n \le 2500, m \le 1000$$$1–3, 5, 6
810$$$n \le 2500, m \le 10^5$$$1–3, 5–7
915$$$n \le 2 \cdot 10^5, m \le 2 \cdot 10^5$$$1–3, 5–8
1020нет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$$$ вариант с нулём расставленных фишек.