你的面前有n个数排成一行。分别为a₁,a₂, … ,a_n。你打算在每相邻的两个ai和ai+1间都插入一个加号或者减号或者乘号。那么一共有3^n-1种可能的表达式。
你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个a_i的值。
你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

第一行包含2个正整数n和Q，为数的个数和询问的个数。
接下来一行 n 个非负整数，依次表示a₁,a₂, … ,a_n。
在接下来Q行，其中第i行两个非负整数ti和vi，表示要将a_ti修改为v_i。其中1≤t_i≤n。
保证对于 1 ≤ j ≤ n, 1 ≤ i ≤ Q，都有a_j,v_i ≤ 10⁴

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