У Эхаба есть массив a из n целых чисел. Он любит операцию побитового исключающего ИЛИ, а ещё он любит надоедать Махмуду, поэтому он придумал для него задачу. Он дал Махмуду q запросов. В каждом из них он дал Махмуду два целых числа l и x и попросил его найти число подпоследовательностей первых l элементов массива таких, что побитовое исключающее ИЛИ всех этих чисел будет равно x. Можете ли вы помочь Махмуду ответить на запросы?
Подпоследовательность может содержать не соседние элементы.
Выходные данные
Для каждого запроса, выведите ответ по модулю 109 + 7 в новой строке.
Примечание
Побитовое исключающее ИЛИ всех чисел пустого множества равно 0, а побитовое исключающее ИЛИ всех чисел множества из одного элемента равно этому элементу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
0 1 2 3 4
4 3
2 0
3 7
5 7
5 8
|
4
2
0
4
0
|
|
2
|
3 2
1 1 1
3 1
2 0
|
4
2
|