rt，明天来看

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,mod=19940417;
namespace SGT{
	#define L (x<<1)
	#define R (x<<1|1)
	int n,a[N],tmp;
	int C[25][25];
	struct node{
		int l,r,sum[25],tag1,tag2;
	}tree[N<<2];
	void init(int x,int c[]){
		n=x;
		for(int i=1;i<=n;i++)
			a[i]=(c[i]%mod+mod)%mod;
		C[0][0]=1;
		for(int i=1;i<=20;i++){
			C[i][0]=1;
			for(int j=1;j<=i;j++)
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
//		for(int i=0;i<=20;i++){
//			for(int j=0;j<=i;j++)
//				cout<<C[i][j]<<' ';
//			cout<<endl;
//		}
	}
	void up(int x){
		for(int i=1;i<=20;i++){
			tree[x].sum[i]=0;
			for(int j=0;j<=i;j++)
				(tree[x].sum[i]+=1ll*tree[L].sum[j]*tree[R].sum[i-j]%mod)%=mod;
		}
	}
	node up(node l,node r){
		node x;
		x.l=l.l;x.r=r.r;
		for(int i=1;i<=20;i++){
			x.sum[i]=0;
			for(int j=0;j<=i;j++)
				(x.sum[i]+=1ll*l.sum[j]*r.sum[i-j]%mod)%=mod;
		}
		return x;
	}
	void maketag1(int x,int k){
		int l=tree[x].r-tree[x].l+1;
		for(int i=min(20,l);i>=1;i--){//len 选 i 固定 j 位 
			tmp=0;int kk=1;
			for(int j=i;j>=0;j--,kk=1ll*kk*k%mod)
				(tmp+=1ll*kk*tree[x].sum[j]%mod*C[l-j][i-j]%mod)%=mod;
			tree[x].sum[i]=tmp;
		}
		(tree[x].tag1+=k)%=mod;
	}
	void maketag2(int x){
		int l=tree[x].r-tree[x].l+1;
		for(int i=min(20,l);i>=1;i--)
			if(i&1)tree[x].sum[i]=(mod-tree[x].sum[i])%mod;
		tree[x].tag2^=1;
		tree[x].tag1=(mod-tree[x].tag1)%mod;
	}
	void spread(int x){
		if(tree[x].tag2){
			maketag2(L);
			maketag2(R);
			tree[x].tag2=0;
		}
		if(tree[x].tag1){
			maketag1(L,tree[x].tag1);
			maketag1(R,tree[x].tag1);
			tree[x].tag1=0;
		}
	}
	void build(int x=1,int lq=1,int rq=n){
		tree[x].l=lq;
		tree[x].r=rq;
		tree[x].sum[0]=1;
		if(lq==rq){
			tree[x].sum[1]=a[lq];
			return;
		}
		int mid=lq+rq>>1;
		build(L,lq,mid);
		build(R,mid+1,rq);
		up(x);
	}
	void modify(int x,int lq,int rq,int k){
		if(lq<=tree[x].l&&tree[x].r<=rq){
			maketag1(x,k);
			return; 
		}
		spread(x);
		int mid=tree[x].l+tree[x].r>>1;
		if(lq<=mid)modify(L,lq,rq,k);
		if(rq>mid)modify(R,lq,rq,k);
		up(x);
	}
	void rever(int x,int lq,int rq){
		if(lq<=tree[x].l&&tree[x].r<=rq){
			maketag2(x);
			return;
		}
		spread(x);
		int mid=tree[x].l+tree[x].r>>1;
		if(lq<=mid)rever(L,lq,rq);
		if(rq>mid)rever(R,lq,rq);
		up(x);
	}
	node query(int x,int lq,int rq){
		if(lq<=tree[x].l&&tree[x].r<=rq)
			return tree[x];
		spread(x);
		int mid=tree[x].l+tree[x].r>>1;
		if(lq<=mid&&rq>mid)
			return up(query(L,lq,rq),query(R,lq,rq));
		else if(lq<=mid)return query(L,lq,rq);
		else if(rq>mid)return query(R,lq,rq);
	}
	#undef L
	#undef R
}
using SGT::init;
using SGT::build;
using SGT::modify;
using SGT::rever;
using SGT::query;
int n,q,a[N];
char op;
int l,r,x;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	init(n,a);
	build();
	while(q--){
		cin>>op>>l>>r;
		if(op=='I'){
			cin>>x;
			modify(1,l,r,(x%mod+mod)%mod);
		}else if(op=='R'){
			rever(1,l,r);
		}else{
			cin>>x;
			cout<<query(1,l,r).sum[x]<<'\n';
		}
	}
	return 0;
}