For an array $$$a$$$, let's define the function $$$f(a)$$$ as the sum of the bitwise XOR sum of each non-empty subsequence$$$^\dagger$$$ of it.
For example, if $$$a$$$ = $$$[5 , 2 , 4]$$$, then $$$f(a) = (5 \oplus 2 \oplus 4) + (5 \oplus 2) + (5 \oplus 4) + (2 \oplus 4) + 5 + 2 + 4$$$.
Let's define an array of arrays $$$A$$$, which contains all non-empty subsequences$$$^\dagger$$$ of the array $$$a$$$.
You are given an array of $$$a$$$ of length $$$n$$$. You have to process the following $$$q$$$ updates:
Since this value could be too large, find it modulo $$$10^9 + 7$$$.
Here $$$\oplus$$$ denotes the bitwise XOR operation.
$$$\dagger$$$ A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) elements. For example, $$$[3,1]$$$ is a subsequence of $$$[3,2,1]$$$ and $$$[4,3,1]$$$, but not a subsequence of $$$[1,3,3,7]$$$ and $$$[3,10,4]$$$.
The first line contains one integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the length of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the elements of the array $$$a$$$.
The third line contains one integer $$$q$$$ $$$(1 \le q \le 10^6)$$$ — the number of update operations.
Each of the next $$$q$$$ lines contains two integers $$$i$$$ and $$$x$$$ $$$(1 \le i \le n, 1 \le x \le 10^9)$$$ — denoting the updated index and value.
After each update, output a single integer — the sum $$$\displaystyle\sum_{s \in A} f(s)$$$, modulo $$$10^9 + 7$$$.
31 2 331 22 52 7
35 72 74
For the first update, $$$A = [[2],[2],[3],[2,2],[2,3],[2,3],[2,2,3]]$$$, then:
$$$f([2]) + f([2]) + f([3]) + f([2,2]) + f([2,3]) + f([2,3]) + f([2,2,3]) = 2 + 2 + 3 + 4 + 6 + 6 + 12 = 35$$$.
