Крабсбургеры

Как известно, главная особенность рецепта Крабсбургера --- это отсутствие какого-либо рецепта. Для того, чтобы иметь хоть какую-то информацию о бургерах, каждый ингридиент имеет некоторую характеристику --- КрабсИндекс. Известно лишь одно: если Крабсбургер был приготовлен с использованием $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