#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=5e4+,Lm=,mod=;

int n,q,t[N],tot,c[N][Lm+],ans[Lm+],tmp[Lm+];

int ls[N<<],rs[N<<],add[N<<],sm[N<<][Lm+];

bool rev[N<<];

char ch;

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return fx?ret:-ret;

}

void upd(int &x){x-=(x>=mod?mod:);}

void init()

{

    c[][]=;

    for(int i=;i<=n;i++)//n!

        for(int j=;j<=i&&j<=Lm;j++)

        {

            c[i][j]=c[i-][j];

            if(j)c[i][j]+=c[i-][j-],upd(c[i][j]);//i-1

        }

}

void pshp(int cr,int l,int mid,int r)

{

    int lm=min(r-l+,Lm),Ls=ls[cr],Rs=rs[cr];

    for(int i=;i<=lm;i++)

    {

        sm[cr][i]=;

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

            sm[cr][i]=(sm[cr][i]+(ll)sm[Ls][j]*sm[Rs][i-j])%mod;

    }

//    printf("pshp l=%d r=%d\n",l,r);

//    for(int i=0;i<=lm;i++)

//        printf(" sm[%d][%d]=%d\n",cr,i,sm[cr][i]);

}

void updt(int cr,int k,int len)

{

    add[cr]+=k; upd(add[cr]);

    int lm=min(Lm,len);

    for(int i=lm;i>=;i--)

        for(int j=,ml=k;j<=i;j++,ml=(ll)ml*k%mod)//j=1 //j<=i not j<=lm

        {

            sm[cr][i]=(sm[cr][i]+(ll)sm[cr][i-j]*ml%mod*c[len-i+j][j])%mod;

//            if(cr==3&&i==2)

//                printf("smi=%d  j=%d sm[i-j]=%d ml=%d c=[%d][%d]=%d\n",sm[cr][i],j,sm[cr][i-j],ml,len-i+j,j,c[len-i+j][j]);

        }

//    printf("updt\n");

//    for(int i=0;i<=lm;i++)

//        printf(" sm[%d][%d]=%d\n",cr,i,sm[cr][i]);

}

void updr(int cr,int lm)

{

    if(add[cr])add[cr]=mod-add[cr]; rev[cr]^=;//add

    for(int i=;i<=lm;i+=)

        if(sm[cr][i]) sm[cr][i]=mod-sm[cr][i];

//    printf("updr\n");

//    for(int i=0;i<=lm;i++)

//        printf(" sm[%d][%d]=%d\n",cr,i,sm[cr][i]);

}

void pshd(int cr,int l,int mid,int r)

{

    int Ls=ls[cr],Rs=rs[cr];

    if(rev[cr])

    {

        rev[cr]=;

        updr(Ls,min(mid-l+,Lm));

        updr(Rs,min(r-mid,Lm));

    }

    if(add[cr])

    {

        int k=add[cr]; add[cr]=;

        updt(Ls,k,mid-l+);  updt(Rs,k,r-mid);

    }

}

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

{

    if(l==r){sm[cr][]=t[l];sm[cr][]=;return;}

    int mid=l+r>>;

    ls[cr]=++tot; build(l,mid,ls[cr]);

    rs[cr]=++tot; build(mid+,r,rs[cr]);

    pshp(cr,l,mid,r);

}

void mdfy(int l,int r,int cr,int L,int R,int v)

{

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

    {

//        printf("mdf: cr=%d l=%d r=%d\n",cr,l,r);

        updt(cr,v,r-l+); return;

    }

    int mid=l+r>>; pshd(cr,l,mid,r);

    if(L<=mid) mdfy(l,mid,ls[cr],L,R,v);

    if(mid<R) mdfy(mid+,r,rs[cr],L,R,v);

    pshp(cr,l,mid,r);

}

void revs(int l,int r,int cr,int L,int R)

{

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

    {

//        printf("rev: cr=%d l=%d r=%d\n",cr,l,r);

        updr(cr,min(r-l+,Lm));

        return;

    }

    int mid=l+r>>; pshd(cr,l,mid,r);

    if(L<=mid) revs(l,mid,ls[cr],L,R);

    if(mid<R) revs(mid+,r,rs[cr],L,R);

    pshp(cr,l,mid,r);

}

void query(int l,int r,int cr,int L,int R,int k)

{

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

    {

        int lm=min(k,r-l+);

        for(int i=k;i>=;i--)

            for(int j=;j<=lm&&j<=i;j++)//j<=i

                ans[i]=(ans[i]+(ll)sm[cr][j]*ans[i-j])%mod;

        return;

    }

    int mid=l+r>>; pshd(cr,l,mid,r);

    if(L<=mid) query(l,mid,ls[cr],L,R,k);

    if(mid<R) query(mid+,r,rs[cr],L,R,k);

}

int main()

{

//    freopen("data.in","r",stdin);

    n=rdn(); q=rdn(); init();

    for(int i=;i<=n;i++) t[i]=rdn()%mod+mod,upd(t[i]);

    tot=; build(,n,); ans[]=;

    for(int i=,a,b,c;i<=q;i++)

    {

        cin>>ch;scanf("%d%d",&a,&b);

        if(ch!='R')scanf("%d",&c);

        if(ch=='I')

        {

            c=c%mod+mod; upd(c);

            mdfy(,n,,a,b,c);

        }

        if(ch=='R') revs(,n,,a,b);

        if(ch=='Q')

        {

            for(int i=;i<=c;i++)ans[i]=;

            query(,n,,a,b,c);

            printf("%d\n",ans[c]);

        }

    }

    return ;

}