P4340 [SHOI2016] Random Sequence

There are $n$ numbers in a row, namely $a_1, a_2, ..., a_n$. You plan to insert a plus, minus, or multiplication sign between each adjacent pair $a_i$ and $a_{i+1}$. Then there are $3^{n-1}$ possible expressions. You are very interested in the sum of the values of all possible expressions. But that would be too easy, so you also plan to support an update operation that modifies the value of some $a_i$. Can you write a program that, after each update, outputs the sum of all possible expressions after the modification? Note that updates are permanent, which means each update is applied on top of the previous one, not on the initial sequence.

The first line contains two positive integers $n$ and $Q$, the number of values and the number of queries. The second line contains $n$ non-negative integers, namely $a_1, a_2, ..., a_n$ in order. The next $Q$ lines each contain two non-negative integers $t$ and $v$, meaning you set $a_t$ to $v$, where $1 \le t \le n$. It is guaranteed that for all $1 \le j \le n$ and all $1 \le i \le Q$, we have $a_j, v_i \le 10^4$.

Output $Q$ lines. For each update, output one line containing a single integer, the sum of all possible expressions after the update, modulo $10^9+7$.

- For 20% of the testdata, $n, Q \le 20$. - For 50% of the testdata, $n, Q \le 1000$. - For 100% of the testdata, $n, Q \le 100000$. - 2023-11-17: Added a set of hack testdata. Translated by ChatGPT 5