E2. Битовая игра (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии количество камней в каждой кучке не фиксировано, и вам нужно вывести количество вариантов игры, в которых выигрывает Боб. Вы можете совершать взломы только если обе версии задачи решены.

Алиса и Боб играют в знакомую игру, в которой они по очереди вынимают камни из $$$n$$$ кучек. Изначально в $$$i$$$-й куче находится $$$x_i$$$ камней, и она имеет значение $$$a_i$$$. Игрок может забрать $$$d$$$ камней из $$$i$$$-й кучи тогда и только тогда, когда выполняются оба следующих условия:

  • $$$1 \le d \le a_i$$$, и
  • $$$x \, \& \, d = d$$$, где $$$x$$$ — текущее количество камней в $$$i$$$-й куче, а $$$\&$$$ обозначает операцию побитового И.

Алиса ходит первой. Игрок, который не может сделать ход, проигрывает.

Вам даны значения $$$a_i$$$ для каждой кучи, но количество камней в $$$i$$$-й куче еще не определено. Для $$$i$$$-й кучи $$$x_i$$$ может быть любым целым числом от $$$1$$$ до $$$b_i$$$ включительно. То есть можно выбрать массив $$$x_1, x_2, \ldots, x_n$$$ такой, что условие $$$1 \le x_i \le b_i$$$ выполняется для всех куч.

Ваша задача — найти количество игр, в которых Боб выигрывает, если оба игрока играют оптимально. Две игры считаются различными, если количество камней хотя бы в одной кучке разное, то есть массивы $$$x$$$ различаются хотя бы в одной позиции.

Поскольку ответ может быть очень большим, выведите результат по модулю $$$10^9 + 7$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$1 \le n \le 10^4$$$) — количество кучек.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i < 2^{30}$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i < 2^{30}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

Для каждого набора входных данных выведите одно целое число — количество игр, в которых Боб выигрывает, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
7
3
1 2 3
3 2 2
1
13
45
5
5 4 7 8 6
4 4 5 5 5
4
6 4 8 8
12 13 14 12
3
92856133 46637598 12345678
29384774 73775896 87654321
2
65 12
110 31
4
677810235 275091182 428565855 720629731
74522416 889934149 3394714 230851724
Выходные данные
4
4
0
6552
722019507
541
665443265
Примечание

В первом наборе входных данных, какие бы значения $$$x_2$$$ и $$$x_3$$$ мы ни выбрали, вторая и третья кучи всегда будут выбраны ровно один раз, прежде чем из них больше нельзя будет взять ни одного камня. Если $$$x_1 = 2$$$, то ни один камень не может быть взят из нее, поэтому Боб сделает последний ход. Если $$$x_1 = 1$$$ или $$$x_1 = 3$$$, то на этой куче можно сделать ровно один ход, поэтому последний ход сделает Алиса. Таким образом, Боб выигрывает, если $$$x = [2, 1, 1]$$$ или $$$x = [2, 1, 2]$$$ или $$$x = [2, 2, 1]$$$ или $$$x = [2, 2, 2]$$$.

Во втором наборе входных данных Боб выигрывает, если $$$x_1 = 14$$$ или $$$x_1 = 30$$$, убрав $$$14 - k$$$ камней, где $$$k$$$ — количество камней, убранных Алисой в свой ход. Боб также выигрывает в случае $$$x_1 = 16$$$ или $$$x_1 = 32$$$, поскольку у Алисы нет ни одного хода в начале.