Это сложная версия задачи. В этой версии гарантируется, что \(q \leq 10^5\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Целочисленная сетка \(A\) с \(p\) строками и \(q\) столбцами называется красивой, если:
- Все элементы сетки являются целыми числами от \(0\) до \(2^{30}-1\), и
- Для любой подсетки XOR значений в углах равен \(0\). Формально, для любых четырех целых чисел \(i_1\), \(i_2\), \(j_1\), \(j_2\) (\(1 \le i_1 < i_2 \le p\); \(1 \le j_1 < j_2 \le q\)) должно выполняться \(A_{i_1, j_1} \oplus A_{i_1, j_2} \oplus A_{i_2, j_1} \oplus A_{i_2, j_2} = 0\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Имеется частично заполненная целочисленная сетка \(G\) с \(n\) строками и \(m\) столбцами, в которой заполнены только \(k\) ячеек. Поликарп хочет узнать, сколькими способами он может распределить целые числа по незаполненным ячейкам, чтобы сетка стала красивой.
Однако Монокарп считает, что эта задача слишком проста. Поэтому он выполнит \(q\) обновлений сетки. В каждом обновлении он будет выбирать незаполненную ячейку и присваивать ей целое число. Заметим, что эти обновления перманентны. То есть изменения, внесенные в сетку, будут применяться при обработке будущих обновлений.
Для каждого из \(q + 1\) состояния сетки (начального состояния и после каждого из \(q\) запросов) определите количество способов, которыми Поликарп может присвоить целые числа незаполненным ячейкам, чтобы сетка стала красивой. Поскольку это число может быть очень большим, от вас требуется только вывести их значения по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите \(q + 1\) строку. В \(i\)-й строке вывода должен содержаться ответ для \(i\)-го состояния решетки по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных мы изначально имеем следующую сетку:
| \(0\) | \(6\) | \(10\) |
| \(6\) | \(0\) | \(12\) |
| \(10\) | \(12\) | \(?\) |
Можно доказать, что единственным допустимым значением для ячейки \((3, 3)\) является \(0\), поэтому первый ответ — \(1\). Для второго запроса ячейка не удовлетворяет условию, поэтому ответ — \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3 8 1
2 1 6
3 2 12
1 2 6
2 2 0
1 3 10
1 1 0
2 3 12
3 1 10
3 3 1
2 5 2 0
1 1 10
1 2 30
2 5 0 2
1 1 10
1 2 30
|
1
0
489373567
651321892
769740174
489373567
|