Problem Description

You are given a sequence $a$ of length $n$.

We define one operation as: simultaneously replace every element $a_i$ in the sequence $a$ with $\bigoplus\limits_{j=1}^i a_j$ (i.e., the XOR sum from $a_1$ to $a_i$), where $\bigoplus$ denotes bitwise XOR, i.e., ^ in C++.

There are $q$ ordered modifications. Each modification gives two integers $x_i, p_i$, meaning to change the value of $a_{x_i}$ to $p_i$. These modifications are not independent; each modification affects all subsequent modifications.

After each modification, you need to find the smallest positive integer $t$ such that after performing the operation $t$ times, the sequence $a$ becomes the same as the sequence $a$ before the operations. It can be proven that such a positive integer $t$ always exists.

Since the answer may be very large, you only need to output the result modulo $(10^9+7)$.

Input Format

The first line contains two integers $n, q$.

The second line contains $n$ integers, representing the given sequence $a$.

The next $q$ lines each contain two integers $x_i, p_i$, representing one modification.

Output Format

Output $q$ lines. On the $i$-th line, output one integer: after the $i$-th modification, the smallest positive integer $t$ that satisfies the requirement, modulo $(10^9+7)$.

3 3
3 1 0
2 2
1 0
2 0

4
2
1

Hint

"Sample Explanation #1"

After the 1st modification, the sequence $a$ is $\{3,2,0\}$. After performing the operation 1 time, the sequence $a$ becomes $\{3,1,1\}$. After 2 times, it becomes $\{3,2,3\}$. After 3 times, it becomes $\{3,1,2\}$. After 4 times, it becomes $\{3,2,0\}$. Therefore, the smallest required positive integer $t$ is $4$.

Constraints

For all data, $1 \le n,q \le 3\times10^5$, $0 \le a_i,p_i \le 10^9$, $1 \le x_i \le n$.

Only if you pass all test points of this problem can you get the score for this problem.

Translated by ChatGPT 5