#include<bits/stdc++.h>
#define pii pair<int,int>
#define pf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define ls now<<1
#define rs now<<1|1
#define QwQ puts("QwQ")
using namespace std;
const int N=50005,M=20,mod=19940417;
int n,q,a[N],c[N][21];
typedef long long ll;
inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		ans=(ans<<3)+(ans<<1)+(c^48);
		c=getchar();
	}
	return ans*f;
}
inline void write(int x)
{
    if(x<0)
    {
        printf("-"),write(-x);
        return;
    }
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int power(int a,int b,int p)
{
	int sum=1;
	while(b)
	{
		if(b&1) sum=(ll)sum*a%p;
		a=(ll)a*a%p;
		b>>=1;
	}
	return sum;
}
struct node
{
	int res[21];
};
node merge(node a,node b)
{
	node ans={0};
	for(int i=0;i<=M;i++)
	{
		for(int j=0;j<=M-i;j++) 
		{
			ans.res[i+j]=ans.res[i+j]+(ll)a.res[i]*(ll)b.res[j]%mod;
			if(ans.res[i+j]>=mod) ans.res[i+j]-=mod;
		}
	}
	return ans;
}
struct SGT
{
	int add[N*4],rev[N*4],L[N*4],R[N*4];
	node t[N*4];
	void build(int now,int l,int r)
	{
		L[now]=l,R[now]=r;
		if(l==r)
		{
			t[now].res[0]=1;
			t[now].res[1]=(a[l]%mod+mod)%mod;
			return;
		}
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		t[now]=merge(t[ls],t[rs]);
		return;
	}
	void push_add(int now,int k)
	{
		for(int i=min(20,R[now]-L[now]+1);i>=1;i--)
		{
			for(int j=0;j<i;j++) 
			{
				t[now].res[i]=t[now].res[i]+(ll)t[now].res[j]*(ll)power(k,i-j,mod)%mod*(ll)c[R[now]-L[now]+1-j][i-j]%mod;
				if(t[now].res[i]>=mod) t[now].res[i]-=mod;
			}
		}
		add[now]=add[now]+k;
		if(add[now]>=mod) add[now]-=mod;
		return;
	}
	void push_rev(int now)
	{
		for(int i=1;i<=20;i+=2) t[now].res[i]=mod-t[now].res[i];
		add[now]=mod-add[now];
		rev[now]^=1;
		return;
	}
	void pushdown(int now,int l,int r)
	{
		int mid=l+r>>1;
		if(rev[now])
		{
			push_rev(ls);
			push_rev(rs);
			rev[now]=0;
		}
		if(add[now])
		{
			push_add(ls,add[now]);
			push_add(rs,add[now]);
			add[now]=0;
		}
		return;
	}
	void updadd(int now,int l,int r,int ql,int qr,int k)
	{
		if(l>=ql&&r<=qr)
		{
			push_add(now,k);
			return;
		}
		pushdown(now,l,r);
		int mid=l+r>>1;
		if(ql<=mid) updadd(ls,l,mid,ql,qr,k);
		if(qr>mid) updadd(rs,mid+1,r,ql,qr,k);
		t[now]=merge(t[ls],t[rs]);
		return;
	}
	void updrev(int now,int l,int r,int ql,int qr)
	{
		if(l>=ql&&r<=qr)
		{
			push_rev(now);
			return;
		}
		pushdown(now,l,r);
		int mid=l+r>>1;
		if(ql<=mid) updrev(ls,l,mid,ql,qr);
		if(qr>mid) updrev(rs,mid+1,r,ql,qr);
		t[now]=merge(t[ls],t[rs]);
		return;
	}
	node query(int now,int l,int r,int ql,int qr)
	{
		if(l>=ql&&r<=qr) return t[now];
		pushdown(now,l,r);
		int mid=l+r>>1;
		if(qr<=mid) return query(ls,l,mid,ql,qr);
		if(ql>mid) return query(rs,mid+1,r,ql,qr);
		return merge(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
	}
}t;
int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=0;i<=n;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=min(i,M);j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	t.build(1,1,n);
	while(q--)
	{
		char op;
		int l,r,k;
		cin>>op;
		l=read(),r=read();
		if(op=='I') k=(read()%mod+mod)%mod,t.updadd(1,1,n,l,r,k);
		if(op=='R') t.updrev(1,1,n,l,r);
		if(op=='Q') k=read(),write(t.query(1,1,n,l,r).res[k]),printf("\n");
	}
	return 0;
}