RT

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=50005;
const int maxm=22;
const int dd=19940417;
const int phidd=17091780;
int n,m;
int sum[maxn],invsum[maxn],a[maxn];
struct nod{
	int val[maxm],lazy1;    bool lazy2;
	inline void init(){
		lazy1=lazy2=0;
		for(int k=0;k<=20;k++)  val[k]=0;
	}
	inline void print(){
		for(int k=0;k<=20;k++)  cout<<val[k]<<" ";
		puts("");
	}
}tree[maxn<<2];
inline int qpow(int x,int p){
	int ans=1;
	while(p){
		if(p&1) ans=ans*x%dd;
		p>>=1;  x=x*x%dd;
	}
	return ans;
}
inline int inv(int x){return qpow(x,phidd-1);}
inline int C(int x,int y){return sum[x]*(invsum[y]*invsum[x-y]%dd)%dd;}
inline int read(){
	int ret=0,f=1;	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline char Fread(){
	char ch=getchar();
	while(!isalpha(ch)) ch=getchar();
	return ch;
}
inline int mod(int x){return x>dd?x-dd:(x<0?x+dd:x);}
inline void reverse(int nod){
	tree[nod].lazy2=!tree[nod].lazy2;
	for(int k=1;k<=20;k+=2) tree[nod].val[k]=-tree[nod].val[k];
}
inline void change(int nod,int n,int c){
	tree[nod].lazy1+=c;
	static int p[maxm];
	int sta=min(20ll,n);
//	cout<<nod<<" "<<n<<" "<<c<<endl;
//	tree[nod].print();
	p[0]=1;
	for(int k=1;k<=sta;k++)  p[k]=p[k-1]*c%dd;
	for(int k=sta;k>=0;k--){
		int val=0;
		for(int j=0;j<=k;j++)
		val=mod(val+tree[nod].val[j]*(C(n-j,k-j)*p[k-j]%dd)%dd);
//		cout<<val<<" ";
		tree[nod].val[k]=val;
	}
//	puts("");
//	tree[nod].print();
}
inline nod merge(nod x,nod y){
	nod ans;   ans.init();
	for(int k=0;k<=20;k++)
	for(int j=0;j<=20-k;j++)
	if(k+j<=20)	ans.val[k+j]=mod(ans.val[k+j]+x.val[k]*y.val[j]%dd);
	return ans;
}
inline void pushdown(int nod,int l,int r){
	int lazy1=tree[nod].lazy1;  bool lazy2=tree[nod].lazy2;
	tree[nod].lazy1=tree[nod].lazy2=0;
	int mid=l+r>>1; int ls=nod<<1,rs=ls+1;
	int szl=mid-l+1,szr=r-mid;
	if(lazy1)	change(ls,szl,lazy1),change(rs,szr,lazy1);
	if(lazy2)   reverse(ls),reverse(rs);
}
inline void pushup(int nod){
	int ls=nod<<1,rs=ls+1;
	tree[nod]=merge(tree[ls],tree[rs]);
}
void build(int nod,int l,int r){
	if(l==r){
		tree[nod].val[0]=1;
		tree[nod].val[1]=a[l];
//		cout<<nod<<" "<<l<<" "<<r<<endl;
//		tree[nod].print();
		return;
	}
	int mid=l+r>>1; int ls=nod<<1,rs=ls+1;
	build(ls,l,mid);    build(rs,mid+1,r);  pushup(nod);
//	cout<<nod<<" "<<l<<" "<<r<<endl;
//	tree[nod].print();
}
void update1(int nod,int l,int r,int ll,int rr,int val){
	if(l==ll&&r==rr){
		change(nod,r-l+1,val);
		return;
	}
	pushdown(nod,l,r);
	int mid=l+r>>1; int ls=nod<<1,rs=ls+1;
	if(rr<=mid){update1(ls,l,mid,ll,rr,val);pushup(nod);return;}
	if(ll>mid){update1(rs,mid+1,r,ll,rr,val);pushup(nod);return;}
	update1(ls,l,mid,ll,mid,val);    update1(rs,mid+1,r,mid+1,rr,val);    pushup(nod);
}
void update2(int nod,int l,int r,int ll,int rr){
	if(l==ll&&r==rr){
		reverse(nod);
		return;
	}
	pushdown(nod,l,r);
	int mid=l+r>>1; int ls=nod<<1,rs=ls+1;
	if(rr<=mid){update2(ls,l,mid,ll,rr);pushup(nod);return;}
	if(ll>mid){update2(rs,mid+1,r,ll,rr);pushup(nod);return;}
	update2(ls,l,mid,ll,mid);    update2(rs,mid+1,r,mid+1,rr);    pushup(nod);
}
nod query(int nod,int l,int r,int ll,int rr){
//	tree[nod].print();
	if(l==ll&&r==rr)    return tree[nod];
	pushdown(nod,l,r);
	int mid=l+r>>1; int ls=nod<<1,rs=ls+1;
	if(rr<=mid)return query(ls,l,mid,ll,rr);
	if(ll>mid)return query(rs,mid+1,r,ll,rr);
	return merge(query(ls,l,mid,ll,mid),query(rs,mid+1,r,mid+1,rr));
}
signed main(){
	n=read();   m=read();
	sum[0]=1;
	for(int k=1;k<=n;k++)   sum[k]=sum[k-1]*k%dd;
	invsum[n]=inv(sum[n]);
	for(int k=n;k>=1;k--)   invsum[k-1]=invsum[k]*k%dd;
	for(int k=1;k<=n;k++)   a[k]=read();
	for(int k=1;k<=n;k++)
	build(1,1,n);
	for(int k=1;k<=n;k++){
		char ch=Fread();    int l,r;
		l=read();   r=read();
		if(ch=='Q'){
			int v=read();
			nod x=query(1,1,n,l,r);
			printf("%lld\n",x.val[v]);
//			x.print();
		}
		if(ch=='I'){
			int val=mod(read()%dd);
			update1(1,1,n,l,r,val);
		}
		if(ch=='R'){
			update2(1,1,n,l,r);
		}
	}
	return 0;
}