你的面前有 $n$ 个数排成一行，分别为 $a_1,a_2,\dots,a_n$。你打算在每相邻的两个 $a_i$ 和 $a_{i+1}$ 间都插入一个加号、减号或者乘号。那么一共有 $3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

输入格式

第一行包含两个正整数 $n$ 和 $Q$，为数的个数和询问的个数。

第二行包含 $n$ 个非负整数，依次表示 $a_1,a_2,\dots,a_n$。

接下来 $Q$ 行，每行包含两个非负整数 $t$ 和 $v$，表示要将 $a_t$ 修改为 $v$，其中 $1\le t\le n$。

保证 $1\le a_i,v\le 10^4$。

输出格式

输出 $Q$ 行。对于每个修改输出一行，包含一个整数，表示修改之后所有可能表达式的和，对 $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

数据范围与提示