| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 2 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
В лаборатории искусственного интеллекта разработали новый метод машинного обучения. В процессе обучения программы используется n итераций. Каждая итерация заключается в том, что обучаемая программа запускается на некотором обучающем наборе.
Были подготовлены обучающие наборы сложности от 0 до k. План обучения задаётся массивом целых чисел [a1, a2, …, an], где ai задаёт сложность набора, используемого на i-й итерации обучения. Для всех i от 1 до n должно выполняться неравенство 0 ≤ ai ≤ k.
Выяснилось, что эффективность плана обучения зависит от битовых представлений сложностей обучающих наборов. Для того, чтобы план был эффективным, необходимо, чтобы для любых двух значений i и j, где 1 ≤ i ≤ j ≤ n, выполнялось (ai and aj) = ai. Напомним, что побитовое «и» (and) двух целых неотрицательных чисел устроено следующим образом: запишем оба числа в двоичной системе счисления, i-й двоичный разряд результата равен 1, если у обоих аргументов он равен 1. Например, (14 and 7) = (11102 and 01112) = 1102 = 6. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как "&", в Паскале как "and".
Однако постоянное использование наборов одной сложности не даёт прогресса в обучении. Чтобы этого избежать, для плана обучения должны быть выполнены m требований следующего вида. Каждое требование задаётся двумя числами li и ri и означает, что ali ≠ ari.
Сотрудники лаборатории хотят найти количество эффективных планов, которые удовлетворяют всем требованиям. Так как это число может быть очень большим, нужно найти его остаток от деления на 109 + 7.
Требуется написать программу, которая по заданным целым числам n и k, а также m требованиям вида li, ri определяет количество эффективных планов, которые удовлетворяют всем требованиям, и выводит остаток от деления этого количества на число 109 + 7.
Первая строка входных данных содержит три целых числа n, m и k — количество итераций обучения, количество требований и максимальную сложность обучающего набора.
Следующие m строк описывают требования, i-я строка содержит два целых числа li, ri, которые означают, что ali ≠ ari, 1 ≤ li < ri ≤ n. Гарантируется, что все требования различны.
Выведите одно целое число — остаток от деления количества эффективных планов, удовлетворяющих всем требованиям, на число 109 + 7.
1 ≤ n ≤ 3 ⋅ 105, 0 ≤ m ≤ 3 ⋅ 105, 0 ≤ k ≤ 1018, ali ≠ ari, 1 ≤ li < ri ≤ n
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 8 | 1 ≤ n ≤ 500, m = 0, 0 ≤ k ≤ 500 | полная | |
| 2 | 20 | 1 ≤ n ≤ 3 ⋅ 105, m = 0, 0 ≤ k ≤ 107 | 1 | первая ошибка |
| 3 | 10 | 1 ≤ n ≤ 3 ⋅ 105, m = 0, 0 ≤ k ≤ 1018 | 1, 2 | первая ошибка |
| 4 | 8 | 1 ≤ n ≤ 50, 0 ≤ m ≤ 50, 0 ≤ k ≤ 50 | первая ошибка | |
| 5 | 16 | 1 ≤ n ≤ 2000, 0 ≤ m ≤ 2000, 0 ≤ k ≤ 107 | 1, 4 | первая ошибка |
| 6 | 6 | 1 ≤ n ≤ 2000, 0 ≤ m ≤ 2000, 0 ≤ k ≤ 1018 | 1, 4, 5 | первая ошибка |
| 7 | 10 | 1 ≤ n ≤ 3 ⋅ 105, 0 ≤ m ≤ 200, 0 ≤ k ≤ 107 | 1, 2, 4 | первая ошибка |
| 8 | 6 | 1 ≤ n ≤ 3 ⋅ 105, 0 ≤ m ≤ 200, 0 ≤ k ≤ 1018 | 1, 2, 3, 4, 7 | первая ошибка |
| 9 | 16 | 1 ≤ n ≤ 3 ⋅ 105, 0 ≤ m ≤ 3 ⋅ 105, 0 ≤ k ≤ 1018 | 1 - 8 | первая ошибка |
Все возможные планы для первого теста: [0,0], [0,1], [0,2], [0,3], [1,1], [1,3], [2,2], [2,3], [3,3]. Для второго теста: [0,1,1], [0,2,2].
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 |
|
|
| 2 |
|
|