You have $n$ numbers arranged in a row, denoted as $a_1, a_2, \dots, a_n$. You intend to insert either a plus sign, a minus sign, or a multiplication sign between every adjacent pair of numbers $a_i$ and $a_{i+1}$. There are $3^{n-1}$ possible expressions in total.

You are interested in the sum of the values of all possible expressions. However, since that is too simple, you also want to support a modification operation that changes the value of a specific $a_i$.

Can you write a program that outputs the sum of all possible expressions after each modification? Note that the modifications are permanent; each modification is based on the state resulting from the previous modification, rather than the initial expression.

Input

The first line contains two positive integers $n$ and $Q$, representing the number of elements and the number of queries, respectively.

The second line contains $n$ non-negative integers, representing $a_1, a_2, \dots, a_n$ in order.

The next $Q$ lines each contain two non-negative integers $t$ and $v$, indicating that $a_t$ is to be changed to $v$, where $1 \leq t \leq n$.

It is guaranteed that for all $1 \leq j \leq n$ and $1 \leq i \leq Q$, $a_j, v_i \leq 10^4$.

Output

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

Examples

Input 1

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

Output 1

890543652
252923708
942282590
228728040
608998099

Subtasks