萌新求助

#include<bits/stdc++.h>
#define N 1000010
#define K 55
#define mod 1000000007 
#define int long long
using namespace std;
int read() {
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return f*res;
}
int qpow(int a1,int a2) {
	int res=1;
	while(a2) {
		if(a2&1) res=1ll*res*a1%mod;
		a1=1ll*a1*a1%mod;
		a2>>=1;
	} return res;
}
int fac[K],inv[K];
int Lag(int n,int m) {
	int res=0;
	if(n<=m+2) {
		for(int i=1; i<=n; i++) res=(res+qpow(i,m))%mod;
	} else {
		int t=1;
		for(int i=1; i<=m+2; i++) t=t*(n-i)%mod;
		int y=0,flag=(m+2)%2?1:-1;
		for(int i=1; i<=m+2; i++) {
			y=(y+qpow(i,m))%mod;
			res=(res+((flag*y+mod)%mod)*t%mod*qpow(n-i,mod-2)%mod*inv[i-1]%mod*inv[m+2-i]%mod+mod)%mod;
			flag=-flag;
		} 
	} return (res+mod)%mod;
}
int n,k,mx[K],mn[K],len[K],c[N],d[N],v[K],w[K],u[K],ans;
int p[K];
signed main() {
	freopen("P7116_14.in","r",stdin);
	n=read(),k=read(),fac[0]=inv[0]=1;
	for(int i=1; i<55; i++) fac[i]=fac[i-1]*i%mod;
	inv[54]=qpow(fac[54],mod-2);
	for(int i=53; i; i--) inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=1; i<=k; i++) mx[i]=w[i]=read(),mn[i]=1,len[i]=w[i];
	for(int i=1; i<=n; i++) {
		c[i]=read(),d[i]=read();
		v[c[i]]+=d[i];
		if(v[c[i]]>=0) mx[c[i]]=min(mx[c[i]],w[c[i]]-v[c[i]]);
		else mn[c[i]]=max(mn[c[i]],-v[c[i]]+1); 
	}
	int flag=1;
	for(int i=1; i<=k; i++) if(v[i]||mn[i]>mx[i]) flag=0;
	if(flag) {puts("-1");return 0;}
	for(int i=1; i<=k; i++) mx[i]=w[i],mn[i]=1,len[i]=w[i];
	for(int i=1; i<=n; i++) c[i+n]=c[i],d[i+n]=d[i];
	for(int i=1; i<=2*n; i++) {
		u[c[i]]+=d[i];
		if(u[c[i]]>=0) mx[c[i]]=min(mx[c[i]],w[c[i]]-u[c[i]]);
		else mn[c[i]]=max(mn[c[i]],-u[c[i]]+1);
		int tlen=max(0ll,mx[c[i]]-mn[c[i]]+1);
		if(tlen<len[c[i]]) {
			int mul=i;
			for(int j=1; j<=k; j++) if(j!=c[i]) {
				if(len[j]<=0) {mul=0;break;}
				mul=mul*len[j]%mod;
			} ans=(ans+mul)%mod;
			if(i>n) {
//				puts("!");
				int X=0x3f3f3f3f;
				for(int j=1; j<=k; j++) {
					if(len[j]<=0) {X=0;break;}
					if(v[j]) X=min(X,(len[j]-1)/abs(v[j]));  
				}
				memset(p,0,sizeof(p));
				p[0]=i,p[1]=n;
				for(int j=1; j<=k; j++) if(j!=c[i]) {
					for(int t=k; t; t--) p[t]=(1ll*p[t-1]*((mod-abs(v[j]))%mod)%mod+mod+1ll*p[t]*len[j]%mod)%mod;
					p[0]=1ll*p[0]*len[j];
				}
				for(int j=0; j<=k; j++) if(p[j]) ans=(ans+p[j]*Lag(X,j)%mod)%mod;
			} len[c[i]]=tlen;
 		}
	} printf("%lld",ans);
}