#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <iostream>

using namespace std;

#define N 50005

#define mod 19940417

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ll long long

int C[N][21],a[N],n,Q;

char s[10];

struct node

{

	ll f[21],tag,add;

	int siz;

	node ()

	{

		memset(f,0,sizeof(f));

		siz=tag=add=0;

	}

	node operator +(const node &b)

	{

		node c;

		c.f[0]=1;

		for(int i=1;i<=20;i++)

		{

			for(int j=0;j<=i;j++)

			{

				c.f[i]+=f[j]*b.f[i-j]%mod;

				c.f[i]%=mod;

			}

		}

		c.siz=siz+b.siz;

		return c;

	}

	void plus(ll x)

	{

		add+=x;

		add%=mod;

		for(int i=min(siz,20);i;i--)

		{

			ll y=x;

			for(int j=1;j<=i;j++)

			{

				f[i]=(f[i]+y*f[i-j]%mod*C[siz-i+j][j]%mod)%mod;

				y=y*x%mod;

			}

		}

	}

	void rev()

	{

		tag^=1;

		add=(mod-add)%mod;

		for(int i=min(siz,20);i;i--)

		{

			if(i&1)f[i]=(mod-f[i])%mod;

		}

	}

}tr[N<<2];

void PushUp(int rt)

{

	tr[rt]=tr[rt<<1]+tr[rt<<1|1];

}

void build(int l,int r,int rt)

{

	if(l==r)

	{

		tr[rt].f[1]=a[l];

		tr[rt].f[0]=tr[rt].siz=1;

		return ;

	}

	int m=(l+r)>>1;

	build(lson);

	build(rson);

	PushUp(rt);

}

void PushDown(int rt)

{

	if(tr[rt].tag)

	{

		tr[rt<<1].rev();

		tr[rt<<1|1].rev();

		tr[rt].tag=0;

	}

	if(tr[rt].add)

	{

		tr[rt<<1].plus(tr[rt].add);

		tr[rt<<1|1].plus(tr[rt].add);

		tr[rt].add=0;

	}

}

void Update(int L,int R,int c,int l,int r,int rt)

{

	if(L<=l&&r<=R)

	{

		tr[rt].plus(c);

		return ;

	}

	PushDown(rt);

	int m=(l+r)>>1;

	if(m>=L)Update(L,R,c,lson);

	if(m<R)Update(L,R,c,rson);

	PushUp(rt);

}

void Update_rev(int L,int R,int l,int r,int rt)

{

	if(L<=l&&r<=R)

	{

		tr[rt].rev();

		return ;

	}

	PushDown(rt);

	int m=(l+r)>>1;

	if(m>=L)Update_rev(L,R,lson);

	if(m<R)Update_rev(L,R,rson);

	PushUp(rt);

}

node query(int L,int R,int l,int r,int rt)

{

	if(L<=l&&r<=R)

	{

		return tr[rt];

	}

	PushDown(rt);

	int m=(l+r)>>1;

	if(m>=R)return query(L,R,lson);

	if(m<L)return query(L,R,rson);

	return query(L,R,lson)+query(L,R,rson);

}

int main()

{

	scanf("%d%d",&n,&Q);

	C[0][0]=1;

	for(int i=1;i<=n;i++)

	{

		C[i][0]=1;

		for(int j=1;j<=20;j++)

		{

			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

		}

	}

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

	}

	build(1,n,1);

	while(Q--)

	{

		int x,y,z;

		scanf("%s%d%d",s,&x,&y);

		if(s[0]=='I')

		{

			scanf("%d",&z);

			Update(x,y,z,1,n,1);

		}else if(s[0]=='R')

		{

			Update_rev(x,y,1,n,1);

		}else

		{

			scanf("%d",&z);

			printf("%lld\n",(query(x,y,1,n,1).f[z]+mod)%mod);

		}

	}

	return 0;

}