Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Махмуд, Эхаб и ещё одна задача про исключающее ИЛИ
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Эхаба есть массив a из n целых чисел. Он любит операцию побитового исключающего ИЛИ, а ещё он любит надоедать Махмуду, поэтому он придумал для него задачу. Он дал Махмуду q запросов. В каждом из них он дал Махмуду два целых числа l и x и попросил его найти число подпоследовательностей первых l элементов массива таких, что побитовое исключающее ИЛИ всех этих чисел будет равно x. Можете ли вы помочь Махмуду ответить на запросы?

Подпоследовательность может содержать не соседние элементы.

Входные данные

Первая строка содержит целые числа n и q (1 ≤ n, q ≤ 105) — число элементов в массиве и число запросов.

В следующей строке содержится n целых чисел a1, a2, ..., an (0 ≤ ai < 220) — элементы массива.

В каждой из следующих q строк содержатся целые числа l и x (1 ≤ l ≤ n, 0 ≤ x < 220) — запросы Эхаба.

Выходные данные

Для каждого запроса, выведите ответ по модулю 109 + 7 в новой строке.

Примеры
Входные данные
5 5
0 1 2 3 4
4 3
2 0
3 7
5 7
5 8
Выходные данные
4
2
0
4
0
Входные данные
3 2
1 1 1
3 1
2 0
Выходные данные
4
2
Примечание

Побитовое исключающее ИЛИ всех чисел пустого множества равно 0, а побитовое исключающее ИЛИ всех чисел множества из одного элемента равно этому элементу.