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