29174번 - Крабсбургеры 다국어

Как известно, главная особенность рецепта Крабсбургера --- это отсутствие какого-либо рецепта. Для того, чтобы иметь хоть какую-то информацию о бургерах, каждый ингридиент имеет некоторую характеристику --- КрабсИндекс. Известно лишь одно: если Крабсбургер был приготовлен с использованием $m$ ингридиентов с КрабсИндексами $a_1, a_2, \cdots, a_m$, то КрабсИндекс получившегося бургера будет равен $a_1 \oplus a_2 \oplus \cdots \oplus a_m$.

Одним солнечным утром в КрастиКрабс зашли $k$ посетителей. Каждый заказал себе фирменный Крабсбургер, причем $i$-й посетитель пожелал, чтобы КрабсИндекс его бургера был не меньше, чем $l_i$, но и не больше, чем $r_i$.

Перед поваром стоит непростая задача --- он должен приготовить все $k$ бургеров, удовлетворив пожелания клиентов, и обязательно использовав все имеющиеся ингридиенты. Перед ним лежит в ряд $n$ ингридиентов. Он $k$ раз должен взять несколько (не меньше одного) ингридиентов из левого конца ряда, и приготовить из них новый бургер, проследив, чтобы он удовлетворял заказу. Повар готовит бургеры в том же порядке, в котором поступили заказы от клиентов.

Помогите ему узнать, сколько существует способов справиться с задачей. Два способа считаются различными, если есть хотя бы один ингридиент, попавший в бургеры к разным клиентам в этих разбиениях.

В первой строке входного файла даны два целых числа $n, k$ ($1 \le n \cdot k \le 100\,000, k \le n$) --- количество ингридиентов и число клиентов.

В следующей строке дано $n$ целых чисел $a_i$ ($0 \le a_i \le 1\,000\,000\,000$) --- КрабсИндексы ингридиентов.

В следующих $k$ строках дано по 2 целых числа $l_i, r_i$ ($0 \le l_i \le r_i \le 1\,000\,000\,000$) --- пожелания о КрабсИндексе от $i$-го клиента.

Выведите одно целое число --- количество искомых разбиений по модулю $1\,000\,000\,007$.

Исключающее или ($\oplus$) --- логическая операция, которая имеет следующую таблицу истинности:

• $0 \oplus 0=0$
• $0 \oplus 1=1$
• $1 \oplus 0=1$
• $1 \oplus 1=0$

<<Исключающее или>> чисел, состоящих из нескольких бит, считается побитово. Например, $2 \oplus 3=1$, $2 \oplus 5=7$, $5 \oplus 5=0$.

Более подробно про <<исключающее или>> можно почитать тут: https://ru.wikipedia.org/wiki/Сложение\_по\_модулю\_2