eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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

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

Однако постоянное использование наборов одной сложности не даёт прогресса в обучении. Чтобы этого избежать, для плана обучения должны быть выполнены m требований следующего вида. Каждое требование задаётся двумя числами l[i] и r[i] и означает, что a[li]a[ri]. Сотрудники лаборатории хотят найти количество эффективных планов, которые удовлетворяют всем требованиям. Так как это число может быть очень большим, нужно найти его остаток от деления на 10^9 + 7.

Напишите программу, которая по заданным целым числам n и k, а также m требованиям вида l[i], r[i] определяет количество эффективных планов, которые удовлетворяют всем требованиям, и выводит остаток от деления этого количества на число 10^9 + 7.

Вхідні дані

Первая строка содержит три целых числа n, m и k (1n3 * 10^5, 0m3 * 10^5, 0k10^18) - количество итераций обучения, количество требований и максимальную сложность обучающего набора.

Следующие m строк описывают требования, i-я строка содержит два целых числа l[i], r[i], которые означают, что a[li]a[ri] (1l[i] < r[i]n). Гарантируется, что все требования различны.

Вихідні дані

Выведите одно целое число - остаток от деления количества эффективных планов, удовлетворяющих всем требованиям, на число 10^9 + 7.

Приклад

Вхідні дані #1
2 0 3
Вихідні дані #1
9
Вхідні дані #2
3 1 2
1 2
Вихідні дані #2
2

Примітка

Все возможные планы для первого теста: [0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 3].

Для второго теста: [0, 1, 1], [0, 2, 2].

Джерело 2019 Всероссийская олимпиада школьников по информатике, Региональный этап, день 1, Москва, 26 января, Задача D