Eva

Time Limit: 20 Sec  Memory Limit: 256 MB

Description

你的面前有N个数排成一行。分别为A1, A2, … , An。你打算在每相邻的两个 Ai和 Ai+1 间都插入一个加号或者

减号或者乘号。那么一共有 3^(n-1) 种可能的表达式。你对所有可能的表达式的值的和非常感兴趣。但这毕竟太

简单了，所以你还打算支持一个修改操作，可以修改某个Ai 的值。你能够编写一个程序对每个修改都输出修改完

之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行， 而不是

在最初的表达式上进行。

Input 

第一行包含 2 个正整数 N 和 Q，为数的个数和询问的个数。

接下来一行 n 个非负整数，依次表示a1,a2...an

在接下来 Q 行，其中第 ?? 行两个非负整数Ti 和Vi，表示要将 Ati 修改为 Vi。其中 1 ≤ Ti ≤ N。

保证对于 1 ≤ J ≤ N, 1 ≤ i≤ Q，都有 Aj,Vi ≤ 10^4。

N,Q<=100000,本题仅有三组数据

Output

输出共 Q 行，其中第 i 行表示第 i 个询问之后所有可能表达式的和，对10^9 + 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

sum[i]=a[1]*a[2]*……*a[i]

sum[i]对答案的贡献，总共要计算2*3^(n-i-1)次（sum[i]后面的符号不能是×，剩下的符号随便选）。sum[n]只计算一次。

线段树维护即可。

？？？+／／／与／／／+？？？可以抵消

/**************************************************************

    Problem: 4597

    User: ictsing

    Language: C++

    Result: Accepted

    Time:324 ms

    Memory:9104 kb

****************************************************************/

 

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

const ll mt = 100000+5;

const ll mod = 1e9+7;

ll sum[mt<<2],val[mt],ji[mt<<2];

ll k[mt];

inline ll read()

{

    ll num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void pushup(ll x)

{

    if(x)

    {

        ji[x]=ji[x<<1]*ji[x<<1|1]%mod;

        sum[x]=(sum[x<<1]*1ll+sum[x<<1|1]*ji[x<<1])%mod;

    }

}

void build(ll rt,ll l,ll r)

{

    if(l==r)

    {

        ji[rt]=val[l];

        sum[rt]=ji[rt]*1ll*k[l]%mod;

        return ;

    }

    ll mid=(l+r)>>1;

    build(rt<<1,l,mid);

    build(rt<<1|1,mid+1,r);

    pushup(rt);

}

void update(ll rt,ll l,ll r,ll x,ll p)

{

    if(l==r)

    {

        ji[rt]=p;

        sum[rt]=ji[rt]*1ll*k[l]%mod;

        return ;

    }

    ll mid=(l+r)>>1;

    if(x<=mid) update(rt<<1,l,mid,x,p);

    else update(rt<<1|1,mid+1,r,x,p);

    pushup(rt);

}

int main()

{

    ll n=read(),q=read();

    for(ll i=1;i<=n;i++) val[i]=read();

    k[n]=1,k[n-1]=2;

    for(ll i=n-2;i>=1;i--) k[i]=1ll*3*k[i+1]%mod;

    build(1,1,n);

    while(q--)

    {

        ll p=read(),x=read();

        update(1,1,n,p,x);

        printf("%lld\n",sum[1]%mod);

    }

    return 0;

}