簡單手摸后發(fā)現(xiàn)，答案就是這么一個式子：

\( (3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dots a_{n-1}+a_1a_2\dots a_n \)

啊當然證明也是好證的，對于 \(a_1\) 這一項，它后面放 + 或 - 都會對系數(shù)加一，而放 * 不會影響系數(shù)，因此系數(shù)就是總數(shù)的三分之二。其它前綴乘積的系數(shù)都是類似的算法。

然后為什么沒有別的項了呢？可以認為 * 不產(chǎn)生貢獻，而 + 和 - 是相同數(shù)量的，因此都消掉了。

簡單預處理，修改時取逆元區(qū)間乘就行了。

但其實不行，因為輸入的是非負數(shù)，而不是正整數(shù)，而 \(0\) 是沒逆元的。

觀察式子，發(fā)現(xiàn)從第一個 \(0\) 往后的項就都是 \(0\) 了。因此可以用一個 set 來維護 \(0\) 的位置。操作時正常操作，把 \(0\) 當成 \(1\) 就行了。查詢時只查 \(1\) 到第一個 \(0\) 的位置前面。

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
	char ch;\
	int fu=1;\
	while(!isdigit(ch=getchar()))\
		fu-=(ch=='-')<<1;\
	x=ch&15;\
	while(isdigit(ch=getchar()))\
		x=(x<<1)+(x<<3)+(ch&15);\
	x*=fu;\
}
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,mod=1e9+7;
int n,m,a[maxn],b[maxn],pw3[maxn];
int sum[maxn<<2],tag[maxn<<2];
il void pushup(int id){
	sum[id]=(sum[lid]+sum[rid])%mod;
}
il void pushtag(int id,int val){
	tag[id]=tag[id]*1ll*val%mod;
	sum[id]=sum[id]*1ll*val%mod;
}
il void pushdown(int id){
	if(tag[id]>1){
		pushtag(lid,tag[id]);
		pushtag(rid,tag[id]);
		tag[id]=1;
	}
}
il void build(int id,int l,int r){
	tag[id]=1;
	if(l==r){
		sum[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	pushup(id);
}
il void upd(int id,int L,int R,int l,int r,int val){
	if(L>=l&&R<=r){
		pushtag(id,val);
		return ;
	}
	pushdown(id);
	int mid=(L+R)>>1;
	if(l<=mid){
		upd(lid,L,mid,l,r,val);
	}
	if(r>mid){
		upd(rid,mid+1,R,l,r,val);
	}
	pushup(id);
}
il int query(int id,int L,int R,int l,int r){
	if(L>=l&&R<=r){
		return sum[id];
	}
	pushdown(id);
	int mid=(L+R)>>1,res=0;
	if(l<=mid){
		(res+=query(lid,L,mid,l,r))%=mod;
	}
	if(r>mid){
		(res+=query(rid,mid+1,R,l,r))%=mod;
	}
	return res;
}
il void debug(int id,int l,int r){
	cout<<id<<" "<<l<<" "<<r<<" "<<sum[id]<<"\n";
	if(l==r){
		return ;
	}
	pushdown(id);
	int mid=(l+r)>>1;
	debug(lid,l,mid);
	debug(rid,mid+1,r);
}
il int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=res*1ll*x%mod;
		}
		x=x*1ll*x%mod,y>>=1;
	}
	return res;
}
set<int> zero;
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	read(n)read(m);
	pw3[0]=1;
	for(int i=1;i<=n;i++){
		read(a[i]);
		if(!a[i]){
			a[i]=1;
			zero.insert(i);
		}
		b[i]=a[i];
		pw3[i]=pw3[i-1]*3ll%mod;
	}
	zero.insert(n+1);
	for(int i=n;i;i--){
		(pw3[i]+=mod-pw3[i-1])%=mod;
	}
	for(int i=2;i<=n;i++){
		a[i]=a[i]*1ll*a[i-1]%mod;
	}
	for(int i=1;i<=n;i++){
		a[i]=a[i]*1ll*pw3[n-i]%mod;
	}
	build(1,1,n);
	while(m--){
		int pos,val;
		read(pos)read(val);
		zero.erase(pos);
		if(!val){
			val=1,zero.insert(pos);
		}
		upd(1,1,n,pos,n,val*1ll*qpow(b[pos],mod-2)%mod);
		b[pos]=val;
		printf("%d\n",*zero.begin()==1?0:query(1,1,n,1,*zero.begin()-1));
	}
	return 0;
}
}
int main(){return asbt::main();}
/*
4 1
1 2 3 4
1 2
*/