Это сложная версия задачи. Единственное отличие заключается в том, что в этой версии количество камней в каждой кучке не фиксировано, и вам нужно вывести количество вариантов игры, в которых выигрывает Боб. Вы можете совершать взломы только если обе версии задачи решены.
Алиса и Боб играют в знакомую игру, в которой они по очереди вынимают камни из \(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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество игр, в которых Боб выигрывает, по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных, какие бы значения \(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\), поскольку у Алисы нет ни одного хода в начале.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|