Source : NOI2016贵州省选
Description
你的面前有n个数排成一行。分别为a1,a2, … ,an。你打算在每相邻的两个ai和ai+1间都插入一个加号或者减号或者乘号。那么一共有3n-1种可能的表达式。
你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了,所以你还打算支持一个修改操作,可以修改某个ai的值。
你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗?注意,修改是永久的,也就是说每次修改都是在上一次修改的基础上进行,而不是在最初的表达式上进行。
Input
第一行包含2个正整数n和Q,为数的个数和询问的个数。
接下来一行 n 个非负整数,依次表示a1,a2, … ,an
在接下来Q行,其中第i行两个非负整数ti和vi,表示要将ati修改为vi。其中1≤ti≤n。
保证对于 1 ≤ j ≤ n, 1 ≤ i ≤ Q,都有aj,vi ≤ 104
Output
输出共Q行,其中第i行表示第i个询问之后所有可能表达式的和,对109+7取模。
Sample Input
5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60
Sample Output
890543652
252923708
942282590
228728040
608998099
Hint