Расстановки фишек
(Время: 1 сек. Память: 64 Мб Сложность: 65%)
Дана квадратная доска размера m×m. Строки и столбцы доски пронумерованы от 1 до m.
Требуется расставить на доске фишки так, чтобы в каждой клетке находилось не более одной фишки. При этом должны выполняться n ограничений. В i-м ограничении заданы два целых числа ri и ci, означающие, что в прямоугольнике, состоящем из клеток с координатами [1…ri]×[1…ci], может находиться не более одной фишки.
Определите остаток от деления количества различных расстановок фишек, удовлетворяющих всем ограничениям, на 109 + 7.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и m – количество ограничений и размер доски (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 109).
Далее следует n строк, в каждой из которых записаны два числа ri и ci (1 ≤ ri, ci ≤ m).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – количество допустимых расстановок фишек, взятое по модулю 109 + 7.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 4
4 4 | 17 |
| 2 | 2 2
1 2
2 1 | 10 |
| 3 | 3 5
2 5
3 4
4 4 | 4480 |
Пояснение
В первом примере на всей доске может быть поставлено не более одной фишки. Есть 4×4 = 16 вариантов поставить одну фишку и 1 вариант с нулём расставленных фишек.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
