1008-[SHOI2016]随机序列_上海历年省选真题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你的面前有N个数排成一行。分别为A₁, A₂, … , A_n。你打算在每相邻的两个 A_i和 A_i+1 间都插入一个加号或者减号或者乘号。那么一共有 3^(n-1) 种可能的表达式。你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个A_i 的值。你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？

注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

输入描述:

第一行包含 2 个正整数 N 和 Q，为数的个数和询问的个数。
接下来一行 n 个非负整数，依次表示a₁,a₂...a_n 
在接下来 Q 行，其中第 ?? 行两个非负整数T_i 和V_i，表示要将 A   t_i修改为 V_i。其中 1 ≤ T_i≤ N。 
保证对于 1 ≤ J ≤ N, 1 ≤ i ≤ Q，都有 A_j,V_i ≤ 10^4。 N,Q ≤ 100000,本题仅有三组数据

输出描述:

输出共 Q 行，其中第 i 行表示第 i 个询问之后所有可能表达式的和，对10^9 + 7 取模。

示例1

输入

复制

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

输出

复制

备注:

对于20%的数据， $n,q\le20$

对于50%的数据， $n,q\le1000$

对于100%的数据， $n,q\le100000$