#include<bits/stdc++.h>
#define mid l+r>>1
#define ls now<<1
#define rs now<<1|1
#define int long long
using namespace std;
const int N=50005,mod=19940417;
int n,m,a[N],c[21][21],p[21];
struct tree{
	int c[21],lzt,l;
	bool op;
	void cl(){
		memset(c,0,sizeof c);
		lzt=l=op=0;
		return;
	}
}tr[N<<2];
void pushup(int now){
	tr[now].l=tr[ls].l+tr[rs].l;
	for(int j=1;j<=min(tr[now].l,(int)20);j++){
		tr[now].c[j]=0;
		for(int i=max((int)0,min(j-tr[ls].l,(int)20));i<=min(tr[rs].l,j);i++)
			tr[now].c[j]+=tr[ls].c[j-i]*tr[rs].c[i],tr[now].c[j]=(tr[now].c[j]%mod+mod)%mod;
	}
}
void build(int l,int r,int now){
	tr[now].c[0]=1;
	if(l==r){
		tr[now].c[1]=a[l];
		tr[now].l=1;
		return;
	}
	build(l,mid,ls);
	build((mid)+1,r,rs);
	pushup(now);
}
int ksm(int x,int f){
	int oth=1,a=x;
	while(f>1){
		if(f&1) oth*=x,oth%=mod;
		a*=a;
		a%=mod;
		f>>=1;
	}
	return ((a*oth)%mod+mod)%mod;
}
void pushdown(int now){
	if(tr[now].lzt!=0){
		tr[ls].lzt+=tr[now].lzt,tr[rs].lzt+=tr[now].lzt;
		for(int i=1;i<=min(tr[ls].l,(int)20);i++)
			for(int j=1;j<=i;j++)
				tr[ls].c[i]+=(tr[ls].c[i-j]*ksm(tr[now].lzt,j))%mod*c[j][tr[ls].l-i+j]%mod,tr[ls].c[i]=(tr[ls].c[i]%mod+mod)%mod;
		for(int i=1;i<=min(tr[rs].l,(int)20);i++)
			for(int j=1;j<=i;j++)
				tr[rs].c[i]+=(tr[rs].c[i-j]*ksm(tr[now].lzt,j))%mod*c[j][tr[rs].l-i+j]%mod,tr[rs].c[i]=(tr[rs].c[i]%mod+mod)%mod;
		tr[now].lzt=0;
	}
	if(tr[now].op){
		for(int i=1;i<=min(tr[now].l/2,(int)20);i+=2)
			tr[ls].c[i]*=-1,tr[rs].c[i]*=-1,tr[ls].c[i]=(tr[ls].c[i]+mod)%mod,tr[rs].c[i]=(tr[rs].c[i]+mod)%mod;
		tr[ls].op^=1,tr[rs].op^=1;
		tr[now].op=0;
	}
}
void update(int l,int r,int now,int ll,int rr,int x){
	if(ll<=l && r<=rr){
		for(int i=1;i<=min(tr[now].l,(int)20);i++)
			for(int j=1;j<=i;j++)
				tr[now].c[i]+=(tr[now].c[i-j]*p[j])%mod*c[j][tr[now].l-i+j]%mod,tr[now].c[i]=(tr[now].c[i]+mod)%mod;
		tr[now].lzt+=x;
		return;
	}
	pushdown(now);
	if(ll<=mid) update(l,mid,ls,ll,rr,x);
	if(rr>mid) update((mid)+1,r,rs,ll,rr,x);
	pushup(now);
}
void nega(int l,int r,int now,int ll,int rr){
	if(ll<=l && r<=rr){
		for(int i=1;i<=min((int)20,tr[now].l);i+=2)
			tr[now].c[i]*=-1,tr[now].c[i]=(tr[now].c[i]+mod)%mod;
		tr[now].op^=1;
		return;
	}
	pushdown(now);
	if(ll<=mid) nega(l,mid,ls,ll,rr);
	if(rr>mid) nega((mid)+1,r,rs,ll,rr);
	pushup(now);
}
tree mg(tree x,tree y){
	if(x.l==0) return y;
	tree res;
	res.cl();
	res.c[0]=1;
	res.l=x.l+y.l;
	if(x.l<y.l){
		for(int i=1;i<=min(res.l,(int)20);i++){
			for(int j=max((int)0,min(i-max(x.l,y.l),(int)20));j<=min(min(x.l,y.l),i);j++)
				res.c[i]+=x.c[j]*y.c[i-j],res.c[i]=(res.c[i]%mod+mod)%mod;
		}
	}
	else for(int i=1;i<=min(res.l,(int)20);i++)
			for(int j=max((int)0,min(i-max(x.l,y.l),(int)20));j<=min(min(x.l,y.l),i);j++)
				res.c[i]+=x.c[i-j]*y.c[j],res.c[i]=(res.c[i]%mod+mod)%mod;
	return res;
}
tree query(int l,int r,int now,int ll,int rr){
	if(ll<=l && r<=rr) return tr[now];
	pushdown(now);
	tree res;
	res.cl();
	if(ll<=mid) res=query(l,mid,ls,ll,rr);
	if(rr>mid){
		tree b=query((mid)+1,r,rs,ll,rr);
		return mg(res,b);
	}
	return res;
}
void zuhe(){
	for(int i=1;i<=20;i++)
		c[0][i]=1,c[1][i]=i,c[i][i]=1;
	for(int i=2;i<=20;i++)
		for(int j=i+1;j<=20;j++){
			c[i][j]=c[i][j-1]+c[i-1][j-1];
        c[i][j]=(c[i][j]%mod+mod)%mod;
     }
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,n,1);
	zuhe();
	p[0]=1;
	char cmd;
	for(int i=1,a,b,c;i<=m;i++){
		cin>>cmd>>a>>b;
		if(cmd=='I'){
			cin>>c;
			for(int j=1;j<=20;j++)
				p[j]=(p[j-1]*c)%mod;
			update(1,n,1,a,b,c);
		}
		if(cmd=='R')
			nega(1,n,1,a,b);
		if(cmd=='Q'){
			cin>>c;
			cout<<(query(1,n,1,a,b).c[c]%mod+mod)%mod<<'\n';
		}
	}
	return 0;
}