求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,K=15;
const int p=1e9+7;
const int inf=1e9+15;
int n,k,a[K],de[K];
int c[N],d[N];
int l[N],r[N],lt[N],rt[N],ans,len[N];
int fac[N],inv[N];
int rx[K],rc[K],h[K];
void add(int &x,int y){
	x=(x+y)%p;
	if(x<0) x+=p;
}
void tim(int &x,int y){
	x=(x*y)%p;
	if(x<0) x+=p;
}
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++){
		fac[i]=fac[i-1]*i%p;
	}
	inv[0]=inv[1]=1;
	for(int i=2;i<N;i++){
		inv[i]=inv[p%i]*(p-p/i)%p;
	}
	for(int i=1;i<N;i++){
		tim(inv[i],inv[i-1]);
	}
}
int qp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) tim(ans,x);
		tim(x,x);
		y>>=1;
	}
	return ans;
}
struct ds{
	int a[N],cl[N],cr[N];
	int sol(int n,int k){
		if(k==0) return n+1;
		*this=ds();
		for(int i=1;i<=k+2;i++){
			cl[i]=cr[i]=(n-i+p)%p;
		}
		cl[0]=cr[k+3]=1;
		for(int i=1;i<=k+2;i++){
			tim(cl[i],cl[i-1]);
		}
		for(int i=k+2;i>=1;i--){
			tim(cr[i],cr[i+1]);
		}
		for(int i=1;i<=k+2;i++){
			a[i]=(a[i-1]+qp(i,k))%p;
		}
		int ans=0;
		for(int i=1;i<=k+2;i++){
			add(ans,a[i]*cl[i-1]%p*cr[i+1]%p*inv[i-1]%p*inv[k+2-i]%p*((k-i+2)%2==0?1:p-1)%p);
		}
		return ans;
	}
}t;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	init();
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>a[i];
		l[i]=1,r[i]=a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>c[i]>>d[i];
		int res=1;
		for(int j=1;j<=k;j++){
			tim(res,r[j]-l[j]+1);
		}
		add(ans,res);
		if(res==0){
			cout<<ans<<"\n";
			return 0;
		}
		l[c[i]]=max(1ll,l[c[i]]+d[i]);
		r[c[i]]=min(a[c[i]],r[c[i]]+d[i]);
		de[c[i]]+=d[i];
	}
	memcpy(lt,l,sizeof(l));
	memcpy(rt,r,sizeof(r));
	int lim=inf;
	for(int i=1;i<=k;i++){
		len[i]=r[i]-l[i]+1;
		if(de[i]!=0) lim=min(lim,len[i]/abs(de[i]));
		rx[i]=-de[i];
		rc[i]=len[i];
	}
	if(lim==inf){
		cout<<"-1\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		int f[K]={},g[K]={};
		f[0]=1;
		for(int j=1;j<=k;j++){
			for(int l=0;l<j;l++){
				add(g[l+1],f[l]*rx[j]);
				add(g[l],f[l]*rc[j]);
			}
			memcpy(f,g,sizeof(f));
			memset(g,0,sizeof(g));
		}
		for(int j=0;j<=k;j++){
			add(h[j],f[j]);
		}
		int g1=r[c[i]]-l[c[i]]+1;
		l[c[i]]=max(1ll,l[c[i]]+d[i]);
		r[c[i]]=min(a[c[i]],r[c[i]]+d[i]);
		int g2=r[c[i]]-l[c[i]]+1;
		rc[c[i]]+=g2-g1;
	}
	for(int j=0;j<=k;j++){
		if(lim) add(ans,h[j]*t.sol(lim-1,j));
	}
	for(int j=0;j<=k;j++){
		len[j]-=de[j]*lim;
	}
	memcpy(l,lt,sizeof(l));
	memcpy(r,rt,sizeof(r));
	for(int i=1;i<=n;i++){
		int res=1;
		for(int j=1;j<=k;j++){
			tim(res,len[j]);
		}
		add(ans,res);
		if(res==0){
			cout<<ans<<"\n";
			return 0;
		}
		int g1=r[c[i]]-l[c[i]]+1;
		l[c[i]]=max(1ll,l[c[i]]+d[i]);
		r[c[i]]=min(a[c[i]],r[c[i]]+d[i]);
		int g2=r[c[i]]-l[c[i]]+1;
		len[c[i]]+=g2-g1;
	}
	cout<<ans<<"\n";
}