Задача . E1. Billetes MX (простая версия)

Это простая версия задачи. В этой версии гарантируется, что \(q = 0\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Целочисленная сетка \(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\).