https://www.luogu.com.cn/discuss/649457
#include<bits/stdc++.h>
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define ll long long
using namespace std;
const int N=5e4+5;
const ll mod=19940417,fu1=((-1)%mod+mod)%mod;
int n,m,rev[N<<2],len[N<<2];
ll add[N<<2],a[N],c[N][21],pw[21];
struct node{
ll f[21];
node(){
memset(f,0,sizeof f);
f[0]=1;
}
}seg[N<<2];
void revnode(int x){
rev[x]^=1;
add[x]=add[x]*fu1%mod;
for(int i=1;i<=min(len[x],20);++i){
if(i&1){
seg[x].f[i]=seg[x].f[i]*fu1%mod;
}
}
}
void addnode(int x,ll d){
node t=seg[x];
add[x]=(add[x]+d)%mod;
for(int i=pw[0]=1;i<=min(len[x],20);++i){
pw[i]=pw[i-1]*d%mod;
}
seg[x]=node();
for(int i=1;i<=min(len[x],20);++i){
for(int j=0;j<=i;++j){
seg[x].f[i]=(seg[x].f[i]+c[len[x]-i+j][j]*pw[j]%mod*t.f[i-j])%mod;
}
}
}
void down(int x){
if(rev[x]){
revnode(ls(x));
revnode(rs(x));
rev[x]=0;
}
if(add[x]){
addnode(ls(x),add[x]);
addnode(rs(x),add[x]);
add[x]=0;
}
}
node merge(node l,node r){
node ret;
for(int i=1;i<=20;++i){
for(int j=0;j<=i;++j){
ret.f[i]=(ret.f[i]+l.f[j]*r.f[i-j])%mod;
}
}
return ret;
}
void build(int x,int l,int r){
len[x]=r-l+1;
if(l==r){
seg[x].f[1]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
seg[x]=merge(seg[ls(x)],seg[rs(x)]);
}
void modify(int x,int l,int r,int ql,int qr,int u,ll v){
if(ql<=l&&r<=qr){
if(u){
revnode(x);
}
if(v){
addnode(x,v);
}
return;
}
down(x);
int mid=(l+r)>>1;
if(ql<=mid){
modify(ls(x),l,mid,ql,qr,u,v);
}
if(qr>mid){
modify(rs(x),mid+1,r,ql,qr,u,v);
}
seg[x]=merge(seg[ls(x)],seg[rs(x)]);
}
node query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return seg[x];
}
down(x);
node ret;
int mid=(l+r)>>1;
if(ql<=mid){
ret=merge(ret,query(ls(x),l,mid,ql,qr));
}
if(qr>mid){
ret=merge(ret,query(rs(x),mid+1,r,ql,qr));
}
return ret;
}
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
c[0][0]=c[1][0]=c[1][1]=1;
for(int i=2;i<=n+1;++i){
c[i][0]=1;
if(i<=20){
c[i][i]=1;
}
for(int j=0;j<=min(20,i-1);++j){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]=(a[i]%mod+mod)%mod;
}
build(1,1,n);
for(char op;m--;){
int l,r;
cin>>op>>l>>r;
if(op=='I'){
ll c;
cin>>c;
c=(c%mod+mod)%mod;
modify(1,1,n,l,r,0,c);
}else if(op=='R'){
modify(1,1,n,l,r,1,0);
}else{
int c;
cin>>c;
cout<<query(1,1,n,l,r).f[c]<<'\n';
}
}
return 0;
}