Description

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.

Input Format

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 Format

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$.

5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60

890543652
252923708
942282590
228728040
608998099

Hint

• 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