description

年级第一的小学生Fkb因为上数学课睡觉被老师点名，老师在黑板上写下了$a_1,a_2,...,a_n$序列 ,让Fkb在相邻两个书之间填上$+,-,\times$中的某一个，并让Fkb计算所有可能的序列的答案之和，Fkb很轻松就答出来的。老师又每次修改某个$a_i$，并让Fkb快速求出每次修改之后的答案，由于修改实在是太多了，Fkb只好求助于你。结果对于$1e9+7$取模。

input

第一行输$n,m$，分别表示序列长度和修改次数
第二行$n$个数,表示初始序列
接下来$m$行，每行两个数字$x,y$，表示将$a_x$修改为y

output

总共$m$行，表示每次修改之后的答案。

sample input

3 1
1 1 2
3 1

sample output

9

limitations

对于30%的数据，$n,m\leq 10$
对于另外20%的数据，$m=1$
对于100%的数据，$n,m\leq 10^5 a_i\leq 10^6$