Cycle Restoration after Prefix XOR Operations

You are given a sequence \(a = [a_1, a_2, \ldots, a_n]\) of length \(n\). We define an operation on \(a\) as follows: simultaneously, for each \(1 \le i \le n\), replace \(a_i\) by the prefix XOR
\[ a_i \leftarrow a_1 \oplus a_2 \oplus \cdots \oplus a_i,\] where \(\oplus\) denotes the bitwise exclusive OR (XOR) (the same as the operator ^ in C++).

There are \(q\) sequential update queries. Each query gives two integers \(x_i\) and \(p_i\) meaning that you should update \(a_{x_i}\) to \(p_i\). The updates are cumulative (each update affects the next ones).

After each update, you are asked to find the minimum positive integer \(t\) such that if you perform the operation exactly \(t\) times (starting from the current sequence) the sequence returns to its original state. In other words, let \(T\) be the transformation defined by the operation; find the smallest \(t>0\) such that \[ T^t(a) = a. \]

Observation: The operation is linear (when seen bitwise over \(\mathbb{F}_2\)). In fact, if we define the transformation matrix \(T\) with entries \[ T_{ij} = \begin{cases} \binom{t}{i-j} \pmod{2} & \text{if } i\ge j, \ 0 & \text{otherwise}, \end{cases} \] then one can show that the full transformation has a cycle length which is always a power of 2. More concretely, if we denote \(t = 2^k\) for some nonnegative integer \(k\), then a necessary and sufficient condition for the sequence \(a\) to return to itself is that for every index \(i\) satisfying \(i-2^k \ge 1\), we have \[ a_{i-2^k} = 0. \]

Thus, if we let \(m = \min\{k \ge 0 : 2^k \ge n\}\), then the operation always has period \(2^m\) when no non‐zero elements force an earlier period. In particular, the answer is the minimum \(2^k\) (with \(0\le k\le m\)) for which for every \(i\) with \(i-2^k \ge 1\) we have \(a_{i-2^k} = 0\). Note that when \(a\) is the all zero sequence, the answer is \(1\) (taking \(k = 0\)).

Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le \text{constraints})\), representing the length of the sequence and the number of update queries.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the initial sequence.

Each of the next \(q\) lines contains two integers \(x_i\) and \(p_i\) \((1 \le x_i \le n)\), meaning that the current value of \(a_{x_i}\) is changed to \(p_i\). The updates are applied in order and are cumulative.

outputFormat

For each update, output a single line containing the minimum positive integer \(t\) (modulo \(10^9+7\)) such that after performing the operation \(t\) times on the current sequence, the sequence returns to itself.

sample

3 3
0 5 0
2 0
1 7
3 7

1
4
4