#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,q,a[200005],zuhe[200005][30],mod=19940417,tmp[30];
ll mymin(ll a,ll b) 
{
	if(a<b) return a;
	else return b;
}
struct Node
{
	ll c[30],sum,taga;
	bool tagm;
	Node(){taga=tagm=sum=0;memset(c,0,sizeof(c));} 
}node[500005];
void csh()
{
	zuhe[0][0]=1;
	for(ll i=1;i<=n;i++)
	{
		zuhe[i][0]=1;
		for(ll j=1;j<=mymin(20ll,i);j++)
		{
			zuhe[i][j]=zuhe[i-1][j]+zuhe[i-1][j-1];
			zuhe[i][j]%=mod;
		}
	}
}
void pushup(ll w)
{
	memset(node[w].c,0,sizeof(node[w].c));
	ll ls=2*w,rs=2*w+1;
	for(ll i=0;i<=mymin(20ll,node[ls].sum);i++)
	{
		for(ll j=0;j<=mymin(20ll-i,node[rs].sum);j++)
		{
			node[w].c[i+j]+=node[ls].c[i]*node[rs].c[j];
		}
	}
	for(ll i=0;i<=mymin(20ll,node[w].sum);i++)
	{
		node[w].c[i]%=mod;
	} 
}
void build(ll w,ll l,ll r)
{
	node[w].sum=r-l+1;
	if(l==r)
	{
		node[w].c[0]=1;
		node[w].c[1]=(a[l]%mod+mod)%mod;
		return ;
	}
	ll mid=(l+r)/2,ls=2*w,rs=2*w+1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(w);
}
void add(ll w,ll k)
{
	if(!w||!k) return ;
	tmp[0]=1;
	for(ll i=1;i<=mymin(2011,node[w].sum);i++)
	{
		tmp[i]=tmp[i-1]*k;
		tmp[i]%=mod;
	}
	for(ll i=mymin(2011,node[w].sum);i;i--)
	{
		for(ll j=0;j<i;j++)
		{
			node[w].c[i]=node[w].c[i]+node[w].c[j]*tmp[i-j]%mod*zuhe[node[w].sum-j][i-j];
			node[w].c[i]%=mod;
		}
	}
	node[w].taga+=k;
	node[w].taga%=mod;
}
void mul(ll w)
{
	if(!w) return ;
	for(ll i=1;i<=mymin(2011,node[w].sum);i++)
	{
		node[w].c[i]=(i%2)?mod-node[w].c[i]:node[w].c[i];
	}
	node[w].taga=mod-node[w].taga;
	node[w].tagm^=1;
}
void pushdown(ll w)
{
	ll ls=w*2,rs=w*2+1;
	if(node[w].tagm)
	{
		mul(ls);
		mul(rs);
		node[w].tagm=0;
	}
	if(node[w].taga)
	{
		add(ls,node[w].taga);
		add(rs,node[w].taga);
		node[w].taga=0;
	}
}
void aadd(ll w,ll l,ll r,ll ql,ll qr,ll k)
{
	if(ql<=l&&r<=qr)
	{
		add(w,k);
		return ;
	}
	pushdown(w);
	ll mid=(l+r)/2,ls=2*w,rs=2*w+1;
	if(ql<=mid) aadd(ls,l,mid,ql,qr,k);
	if(qr>mid) aadd(rs,mid+1,r,ql,qr,k);
	pushup(w);
}

void amul(ll w,ll l,ll r,ll ql,ll qr)
{
	if(ql<=l&&r<=qr)
	{
		mul(w);
		return ;
	}
	pushdown(w);
	ll mid=(l+r)/2,ls=2*w,rs=2*w+1;
	if(ql<=mid) amul(ls,l,mid,ql,qr);
	if(qr>mid) amul(rs,mid+1,r,ql,qr);
	pushup(w);
}
Node hb(Node x,Node y)
{
	Node z;
	z.sum=x.sum+y.sum;
	for(ll i=0;i<=mymin(20ll,x.sum);i++)
	{
		for(ll j=0;j<=mymin(20ll-i,y.sum);j++)
		{
			z.c[i+j]=z.c[i+j]+x.c[i]*y.c[j];
			z.c[i+j]%=mod;
		}
	}
	return z;
}
Node getsum(ll w,ll l,ll r,ll ql,ll qr)
{
	if(ql<=l&&r<=qr)
	{
		return node[w];
	}
	pushdown(w);
	int mid=(l+r)/2,ls=2*w,rs=2*w+1;
	if(qr<=mid) return getsum(ls,l,mid,ql,qr);
	else if(ql>mid) return getsum(rs,mid+1,r,ql,qr);
	else return hb(getsum(ls,l,mid,ql,qr),getsum(rs,mid+1,r,ql,qr));
}
int main()
{
	cin>>n>>q;
	for(ll i=1;i<=n;i++) cin>>a[i];
	node[0].c[0]=1;
	csh();
	build(1,1,n);
	while(q--)
	{
		char cc;
		ll a,b,c;
		cin>>cc>>a>>b;
		if(cc=='I')
		{
			cin>>c;
			c=(c%mod+mod)%mod;
			aadd(1,1,n,a,b,c);
		}
		else if(cc=='R')
		{
			amul(1,1,n,a,b);
		}
		else
		{
			cin>>c;
			cout<<(getsum(1,1,n,a,b).c[c]%mod+mod)%mod<<endl;
		}
	}
	return 0;
}

0pts 求 助