Машинное обучение

В лаборатории искусственного интеллекта разработали новый метод машинного обучения. В процессе обучения программы используется n итераций. Каждая итерация заключается в том, что обучаемая программа запускается на некотором обучающем наборе.

Были подготовлены обучающие наборы сложности от 0 до k. План обучения задаётся массивом целых чисел [a₁, a₂, ... , a_n], где a_i задаёт сложность набора, используемого на i-й итерации обучения. Для всех i от 1 до n должно выполняться неравенство 0 ⩽ a_i ⩽ k.

Выяснилось, что эффективность плана обучения зависит от битовых представлений сложностей обучающих наборов. Для того, чтобы план был эффективным, необходимо, чтобы для любых двух значений i и j, где 1 ⩽ i < j ⩽ n, выполнялось (a_i and a_j ) = a_i . Напомним, что побитовое «и» (and) двух целых неотрицательных чисел устроено следующим образом: запишем оба числа в двоичной системе счисления, i-й двоичный разряд результата равен 1, если у обоих аргументов он равен 1. Например, (14 and 7) = (1110₂ and 0111₂) = 110₂ = 6. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «&», в Паскале как «and».

Однако постоянное использование наборов одной сложности не даёт прогресса в обучении. Чтобы этого избежать, для плана обучения должны быть выполнены m требований следующего вида. Каждое требование задаётся двумя числами l_i и r_i и означает, что a_li ≠ a_ri.

Сотрудники лаборатории хотят найти количество эффективных планов, которые удовлетворяют всем требованиям. Так как это число может быть очень большим, нужно найти его остаток от деления на 10⁹+7.

Требуется написать программу, которая по заданным целым числам n и k, а также m требованиям вида l_i, r_i определяет количество эффективных планов, которые удовлетворяют всем требованиям, и выводит остаток от деления этого количества на число 10⁹+7.

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа n, m и k — количество итераций обучения, количество требований и максимальную сложность обучающего набора (1 ⩽ n ⩽ 3×10⁵, 0 ⩽ m ⩽ 3×10⁵, 0 ⩽ k ⩽ 10¹⁸). Следующие m строк описывают требования, i-я строка содержит два целых числа l_i, r_i, которые означают, что a_li ≠ a_ri (1 ⩽ l_i < r_i ⩽ n). Гарантируется, что все требования различны.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число — остаток от деления количества эффективных планов, удовлетворяющих всем требованиям, на число 10⁹+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].

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]