Региональные: Первый тур

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

Были подготовлены обучающие наборы сложности от \(0\) до \(k\). План обучения задаётся массивом целых чисел \([a_1, a_2, \dots, a_n]\), где \(a_i\) задаёт сложность набора, используемого на \(i\)-й итерации обучения. Для всех \(i\) от \(1\) до \(n\) должно выполняться неравенство \(0 \le a_i \le k\).

Выяснилось, что эффективность плана обучения зависит от битовых представлений сложностей обучающих наборов. Для того, чтобы план был эффективным, необходимо, чтобы для любых двух значений \(i\) и \(j\), где \(1 \leq i \lt 800 j \leq n\), выполнялось \((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_{l_i} \ne a_{r_i}\).

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

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