#include<bits/stdc++.h>
using namespace std;
char d;
long long ans=0,n,q,k=1,s[100001],a,b,c;
void jia(long long x,long long y,long long z){
	for(long long j=x;j<=y;j++){
		s[j]+=z;
	}
}
void jian(long long x,long long y){
	for(long long j=x;j<=y;j++){
		s[j]=-s[j];
	}
}
void jiang(long long x,long long y,long long z){
	if(z>0){
		for(long long j=x;j<=y;j++){
			k*=s[j];
			k=k%19940417;
			//cout<<j<<" "<<s[j]<<" "<<k<<endl;
			jiang(j+1,y,z-1);
			k/=s[j];
		}
	}
	else{
		ans+=k;
	//	cout<<"   "<<ans<<endl;
	}
	return;
}
int main(){
	//freopen("Q.in","r",stdin);
	cin>>n>>q;
	for(long long i=1;i<=n;i++){
		cin>>s[i];
	}
	for(long long i=1;i<=q;i++){
		cin>>d;
		if(d=='I'){
			cin>>a>>b>>c;
			jia(a,b,c);
			/*for(long long j=1;j<=n;j++){
				cout<<" "<<s[j]<<endl;
			}*/
		}
		else if(d=='R'){
			cin>>a>>b;
			jian(a,b);
			/*for(long long j=1;j<=n;j++){
				cout<<" "<<s[j]<<endl;
			}*/
		}
		else if(d=='Q'){
			ans=0;
			k=1;
			cin>>a>>b>>c;
			jiang(a,b,c);
			cout<<ans<<endl;
		}
	} 
	//fcose(stdin);
	
	return 0;
}