快省选了从数论回来练练数据结构，然后被安利去做了这道毒瘤题。
看到$3$操作。
之后看到$c$的范围只有$20$，明显是暴力维护$20$种答案。
又到了欢乐的推式子时间：
设$f_p(i)$为线段树$p$节点代表区间选$i$个数相乘所有方案得到的和，$ls(p)、rs(p)$为$p$的左右儿子。
合并
对于一个$f_p(i)$，$ls(p)$和$rs(p)$都可以提供各自的$f_{ls(p)}(i)$和$f_{rs(p)}(i)$。
然后就是两个儿子交起来的贡献，可以理解为把两个儿子拼起来，为$\sum\limits_{j=1}^{i-1}f_{ls(p)}(j)f_{rs(p)}(i-j)$。
总复杂度为$O(20^2)$
相反数
区间加太麻烦了先说取反。
容易想到，$i$为奇数，取反会使$f_p(i)$也取反；$i$为偶数则不变。
复杂度为$O(20)$
区间加
比如说$p$有四个数$a,b,c,d$，$f_p(3)$就有$a*b*c,a*b*d,a*c*d,b*c*d$
然后统一加上$k$，再手推一下新的答案，为$4k^3+3k^2(a+b+c)+2k(ab+ac+bc)+abc$
我们可以猜想更新后答案变为$\sum\limits_{j=0}^{i}a_jk^{i-j}f_p(j)$，$a_j$为系数。
问题就变成了求$a_j$。以$a_2$为例，因为$f_p(2)$包含的每种组合的系数都是$a_2$的，所以只要知道任意一项的系数就行了，于是来推一下$a*b$的系数。
$a_2$实际上就是$f_p(3)$所有组合中，可以提取出$a*b$的数量。我们可以用组合数来推：
$p$有$4$个数，选了$2$个数$a,b$后还有$4-2$个数可以选，现在要凑成$3$个数还需要$3-2$个数，即$C^{3-2}_{4-2}$
推广到所有情况，设$siz$为区间长度。$a_j=C_{siz-j}^{i-j}$
式子就变成了$\sum\limits_{j=0}^{i}C_{siz-j}^{i-j}k^{i-j}f_p(j)$
组合数可以杨辉三角预处理。这个式子的复杂度就是$O(20^2*\log 20)$。
取反标记优先，取反时把加法标记一起取反。
总复杂度为$O(n\log n20^2\log 20)=O(大常数*n\log^3 n)$
$emm…$
然后按这个思路写就$A$了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 50005
const int N = 20;
const long long mod = 19940417;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int n,a[maxn];
long long c[maxn][21],ans[21];
long long quickpow(long long x,long long y){
long long an=1;
while(y){
if(y&1)an=an*x%mod;
x=x*x%mod;
y>>=1;
}
return an;
}
struct Segment_Tree{
long long sum[maxn<<2][21],tag[maxn<<2];
int siz[maxn<<2],li[maxn<<2];
//siz为区间长度，li为min(siz,N)，在build是处理出来
bool rev[maxn<<2];
//取反标记
#define ls(x) x<<1
#define rs(x) x<<1|1
inline void update(int node){
for(register int i=1;i<=li[node];++i){
sum[node][i]=(sum[ls(node)][i]+sum[rs(node)][i])%mod;
for(register int j=1;j<i;++j)
sum[node][i]=(sum[node][i]+sum[ls(node)][j]*sum[rs(node)][i-j])%mod;
}
}
inline void datadown(int node,long long d){
for(register int i=li[node];i;--i)
for(register int j=0;j<i;++j)
sum[node][i]=(sum[node][i]+sum[node][j]*c[siz[node]-j][i-j]%mod*quickpow(d,i-j))%mod;
tag[node]=(tag[node]+d)%mod;
}//区间加
inline void reverdown(int node){
for(register int i=1;i<=li[node];i+=2)
sum[node][i]=-sum[node][i];//奇数取反
rev[node]^=1,tag[node]=-tag[node];//加法标记一并取反
}//取反
inline void pushdown(int node){
if(rev[node]){
reverdown(ls(node)),reverdown(rs(node));
rev[node]=false;
}
if(tag[node]){
datadown(ls(node),tag[node]);
datadown(rs(node),tag[node]);
tag[node]=0;
}
}
void build(int l,int r,int node){
siz[node]=r-l+1,li[node]=min(r-l+1,N),sum[node][0]=1;
if(l==r){
sum[node][1]=a[l];
return;
}
int mid=l+r>>1;
build(l,mid,ls(node));
build(mid+1,r,rs(node));
update(node);
}
void add(int L,int R,int l,int r,int node,long long d){
if(L<=l&&R>=r){
datadown(node,d);
return;
}
pushdown(node);
int mid=l+r>>1;
if(L<=mid)add(L,R,l,mid,ls(node),d);
if(R>mid)add(L,R,mid+1,r,rs(node),d);
update(node);
}
void reverse(int L,int R,int l,int r,int node){
if(L<=l&&R>=r){
reverdown(node);
return;
}
pushdown(node);
int mid=l+r>>1;
if(L<=mid)reverse(L,R,l,mid,ls(node));
if(R>mid)reverse(L,R,mid+1,r,rs(node));
update(node);
}
void ask(int L,int R,int l,int r,int node,int c){
if(L<=l&&R>=r){
for(register int i=c;i;--i){
ans[i]=(ans[i]+sum[node][i])%mod;
for(register int j=1;j<i;++j)
ans[i]=(ans[i]+ans[j]*sum[node][i-j])%mod;
}
return;
}
pushdown(node);
int mid=l+r>>1;
if(L<=mid)ask(L,R,l,mid,ls(node),c);
if(R>mid)ask(L,R,mid+1,r,rs(node),c);
}
}st;
void Get_C(){
c[0][0]=1;
for(register int i=1;i<=n;++i){
c[i][0]=1;
for(register int j=1;j<=N;++j)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}//预处理组合数
int main(){
n=read();
int m=read();
Get_C();
for(register int i=1;i<=n;++i)
a[i]=read();
st.build(1,n,1);
char s[2];
int l,r,d;
while(m--){
scanf("%s",s);
l=read(),r=read();
if(s[0]=='R')st.reverse(l,r,1,n,1);
else {
d=read();
if(s[0]=='I')st.add(l,r,1,n,1,d);
else {
memset(ans,0,sizeof ans);
st.ask(l,r,1,n,1,d);
printf("%lld\n",(ans[d]%mod+mod)%mod);
//负数要模成正数输出
}
}
}
}
