Машинное обучение
Машинное обучение
В лаборатории искусственного интеллекта разработали новый метод машинного обучения. В процессе обучения программы используется 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 (1 ≤ n ≤ 3 * 105
, 0 ≤ m ≤ 3 * 105
, 0 ≤ k ≤ 1018
) - количество итераций обучения, количество требований и максимальную сложность обучающего набора.
Следующие m строк описывают требования, i-я строка содержит два целых числа li
, ri
, которые означают, что ali
≠ ari
(1 ≤ li
< ri
≤ n). Гарантируется, что все требования различны.
Выходные данные
Выведите одно целое число - остаток от деления количества эффективных планов, удовлетворяющих всем требованиям, на число 109
+ 7.
Пояснение
Все возможные планы для первого теста: [0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 3].
Для второго теста: [0, 1, 1], [0, 2, 2].
2 0 3
9
3 1 2 1 2
2