原谅我的码风，跪求神犇orz

#include<bits/stdc++.h>
#define int long long
#define len(p) (tr[p].r-tr[p].l+1)
using namespace std;
inline int read()
{
	int f = 1,x = 0; char ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-')f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x=(x << 1)+(x << 3)+(ch ^ 48); ch = getchar();}
	return f*x;
}
const int N=5e4+5,mod=19940417;
struct stree{
	int l,r;
	int val[21],adds;
	bool oppo;
}tr[N<<2];
int mi[21],C[N][21];
inline void push_up(int p){
	memset(tr[p].val,0,sizeof(tr[p].val));
	for(int i=0;i<=min(len(p<<1),20ll);i++)
	for(int j=0;i+j<=20 && j<=len(p<<1|1);j++)
		tr[p].val[i+j]=(tr[p].val[i+j]+1ll*tr[p<<1].val[i]*tr[p<<1|1].val[j]+mod)%mod;
}
inline void build(int rand1,int rand2,int p){
	tr[p].l=rand1,tr[p].r=rand2;
	if(tr[p].l==tr[p].r){
		tr[p].val[0]=1,
		tr[p].val[1]=(read()%mod+mod)%mod;
		return;
	}
	int mid=tr[p].l+tr[p].r>>1;
	build(rand1,mid,p<<1),build(mid+1,rand2,p<<1|1);
	push_up(p);
}
inline void push_down(int p){
	if(tr[p].oppo){
		for(int i=1;i<=min(len(p<<1),20ll);i+=2)
			tr[p<<1].val[i]=mod-tr[p<<1].val[i];
		tr[p<<1].adds=mod-tr[p<<1].adds,tr[p<<1].oppo^=1;
		for(int i=1;i<=min(len(p<<1|1),20ll);i+=2)
			tr[p<<1|1].val[i]=mod-tr[p<<1|1].val[i];
		tr[p<<1|1].adds=mod-tr[p<<1|1].adds,tr[p<<1|1].oppo^=1;
		tr[p].oppo=0;
	}
	if(tr[p].adds){
		mi[0]=1;
		for(int i=1;i<=min(len(p),20ll);i++)
			mi[i]=1ll*mi[i-1]*tr[p].adds%mod;
		for(int i=min(len(p<<1),20ll);i;i--)
		for(int j=0;j<i;j++)
			tr[p<<1].val[i]=(tr[p<<1].val[i]+1ll*tr[p<<1].val[j]*mi[i-j]*C[len(p<<1)-j][i-j])%mod;
		for(int i=min(len(p<<1|1),20ll);i;i--)
		for(int j=0;j<i;j++)
			tr[p<<1|1].val[i]=(tr[p<<1|1].val[i]+1ll*tr[p<<1|1].val[j]*mi[i-j]*C[len(p<<1|1)-j][i-j])%mod;
		tr[p<<1].adds=(1ll*tr[p<<1].adds+tr[p].adds)%mod,tr[p<<1|1].adds=(1ll*tr[p<<1|1].adds+tr[p].adds)%mod;
		tr[p].adds=0;
	}
}
inline void update_adds(int p,int aim1,int aim2,int k){
	if(tr[p].l>=aim1 && tr[p].r<=aim2){
		mi[0]=1;
		for(int i=1;i<=min(len(p),20ll);i++)
			mi[i]=1ll*mi[i-1]*k%mod;
		for(int i=min(len(p),20ll);i;i--)
		for(int j=0;j<i;j++)
			tr[p].val[i]=(tr[p].val[i]+1ll*tr[p].val[j]*mi[i-j]*C[len(p)-j][i-j])%mod;
		tr[p].adds=(1ll*tr[p].adds+k)%mod;
		return;
	}
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(mid>=aim1) update_adds(p<<1,aim1,aim2,k);
	if(mid<aim2) update_adds(p<<1|1,aim1,aim2,k);
	push_up(p);
}
inline void update_oppo(int p,int aim1,int aim2){
	if(tr[p].l>=aim1 && tr[p].r<=aim2){
		for(int i=1;i<=min(len(p),20ll);i+=2)
			tr[p].val[i]=mod-tr[p].val[i];
		tr[p].adds=mod-tr[p].adds,tr[p].oppo^=1;
		return;
	}
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(mid>=aim1) update_oppo(p<<1,aim1,aim2);
	if(mid<aim2) update_oppo(p<<1|1,aim1,aim2);
	push_up(p);
}
inline stree merge(stree t1,stree t2){
	stree res;res.l=t1.l,res.r=t2.r;
	memset(res.val,0,sizeof(res.val));
	for(int i=0;i<=min(20ll,t1.r-t1.l+1);i++)
	for(int j=0;i+j<=20 && j<=t2.r-t2.l+1;j++)
		res.val[i+j]=(res.val[i+j]+1ll*t1.val[i]*t2.val[j])%mod;
	return res;
}
inline stree find(int p,int aim1,int aim2){
	if(tr[p].l>=aim1 && tr[p].r<=aim2) return tr[p];
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(mid>=aim2) return find(p<<1,aim1,aim2);
	if(mid<aim1) return find(p<<1|1,aim1,aim2);
	return merge(find(p<<1,aim1,aim2),find(p<<1|1,aim1,aim2));
}
signed main()
{
	int n=read(),q=read(),l,r,k;char opt;
	build(1,n,1);
	tr[0].val[0]=C[0][0]=1;
	for(int i=1;i<=n;i++){
		C[i][0]=1;
		for(int j=1;j<=min(20ll,i);j++)
			C[i][j]=(1ll*C[i-1][j]+C[i-1][j-1])%mod;
	}
	while(q--){
		opt=getchar();
		while(opt!='I' && opt!='R' && opt!='Q') opt=getchar();
		l=read(),r=read();
		switch(opt){
			case 'I':
				k=(1ll*read()%mod+mod)%mod;
				update_adds(1,l,r,k);
				break;
			case 'R':
				update_oppo(1,l,r);
				break;
			case 'Q':
				k=read();
				printf("%d\n",(1ll*find(1,l,r).val[k]%mod+mod)%mod);
				break;
		}
	}
	return 0;
}