自制题求解法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60,Mod=1e9+7,M=100004;
int Pas[N][N],a[M];
int Pow(int a,int p){
	int res=1;
	while(p){
		if(p&1) res=(res*a)%Mod;
		a=(a*a)%Mod;
		p>>=1;
	}
	return res%Mod;
}
void Pre(int n){
	for(int i=0;i<=n;i++){
		Pas[i][0]=1ll;
		for(int j=1;j<=i;j++){
			Pas[i][j]=(Pas[i-1][j]+Pas[i-1][j-1])%Mod;
		}
	}
}
struct St{
#define ls u<<1
#define rs (u<<1)+1
#define mid ((l+r)>>1)
	struct Node{
		int tag[N];
		int add,mul,alt;
		void U_Alt(int x,int l,int r){
			x%=Mod;
			for(int i=1;i<=50;i++){
				tag[i]=(r-l+1)*Pow(x,i)%Mod;
			}
			alt=x,mul=1,add=0;
		}
		void U_Mul(int x){
			x%=Mod;
			for(int i=1;i<=50;i++){
				tag[i]=tag[i]*Pow(x,i)%Mod;
			}
			mul=mul%Mod*x%Mod;
			add=add%Mod*x%Mod;
		}
		void U_Add(int x,int l,int r){
			x%=Mod;
			for(int i=50;i>=1;i--){
				for(int j=1;j<=i-1;j++){
					tag[i]=(tag[i]%Mod+Pas[i][j]%Mod*tag[i-j]%Mod*Pow(x,j)%Mod)%Mod;
				}
				tag[i]=(tag[i]+Pow(x,i)%Mod*(r-l+1)%Mod)%Mod;
			}
//			cout<<tag[1]<<' '<<tag[2]<<' '<<tag[3]<<'\n';
			add=(add%Mod+x)%Mod;
		}
	};
	vector<Node>tr;
	void init(int n){
		tr.resize(4*n+1);
		build(1,1,n);
	}
	void pushup(int u){
		for(int i=1;i<=50;i++){
			tr[u].tag[i]=(tr[ls].tag[i]+tr[rs].tag[i])%Mod;
		}
	}
	void pushdown(int u,int l,int r){
		if(tr[u].alt!=0){
			tr[ls].U_Alt(tr[u].alt,l,mid);
			tr[rs].U_Alt(tr[u].alt,mid+1,r);
			tr[u].alt=0;
		}
		if(tr[u].mul!=1){
			tr[ls].U_Mul(tr[u].mul);
			tr[rs].U_Mul(tr[u].mul);
			tr[u].mul=1;
		}
		if(tr[u].add!=0){
			tr[ls].U_Add(tr[u].add,l,mid);
			tr[rs].U_Add(tr[u].add,mid+1,r);
			tr[u].add=0;
		}
		return;
	}
	void build(int u,int l,int r){
		tr[u].add=tr[u].alt=0,tr[u].mul=1;
		if(l==r){
			for(int i=1;i<=50;i++) tr[u].tag[i]=Pow(a[l],i)%Mod;
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(u);
	}
	void Alt(int u,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			tr[u].U_Alt(val,l,r);
			return;
		}
		pushdown(u,l,r);
		if(mid>=ql) Alt(ls,l,mid,ql,qr,val);
		if(mid<qr) Alt(rs,mid+1,r,ql,qr,val);
		pushup(u);
	}
	void Mul(int u,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			tr[u].U_Mul(val);
			return;
		}
		pushdown(u,l,r);
		if(mid>=ql) Mul(ls,l,mid,ql,qr,val);
		if(mid<qr) Mul(rs,mid+1,r,ql,qr,val);
		pushup(u);
	}
	void Add(int u,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			tr[u].U_Add(val,l,r);
			return;
		}
		pushdown(u,l,r);
		if(mid>=ql) Add(ls,l,mid,ql,qr,val);
		if(mid<qr) Add(rs,mid+1,r,ql,qr,val);
		pushup(u);
	}
	int query(int u,int l,int r,int ql,int qr,int t){
		if(ql<=l&&r<=qr){
			return tr[u].tag[t]%Mod;
		}
		pushdown(u,l,r);
		int res=0;
		if(mid>=ql) res=(res%Mod+query(ls,l,mid,ql,qr,t))%Mod;
		if(mid<qr) res=(res%Mod+query(rs,mid+1,r,ql,qr,t))%Mod;
		return res%Mod;
	}
};
int n,m;
void Solve(){
	St st;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	st.init(n);
	for(int i=1;i<=m;i++){
		int op,l,r,p;
		cin>>op>>l>>r>>p;
		if(op==1){
			st.Add(1,1,n,l,r,p);
		}
		if(op==2){
			st.Mul(1,1,n,l,r,p);
		}
		if(op==3){
			st.Alt(1,1,n,l,r,p);
		}
		if(op==4){
			cout<<((st.query(1,1,n,l,r,p)+Mod)%Mod+Mod)%Mod<<'\n';
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Pre(50);
//	cout<<Pow(-2,19);
	while(cin>>n>>m){
		if(n==0&&m==0) return 0;
		Solve();
	}
	return 0;
}