RT，样例过了，但是不知道为什么全WA

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 50010, P = 19940417;
int n, m;
int a[N], C[N][21];

struct node {
	int sz, c[21];
	int ad, f;
}t[N << 2], Empty;

bool operator == (node a, node b) {
	return a.sz == b.sz && a.c[0] == b.c[0];
}
//预处理C数组（组合数）
void init() {
	t[0].c[0] = 1;
	C[0][0] = 1;
	for(int i = 1;i <= n;i ++) {
		C[i][0] = 1;
		for(int j = 1;j <= i && j <= 20;j ++){
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
		}
	}
	Empty.c[0] = -1; 
	Empty.sz = 0;
}
//修改
void update(int q) {
	memset(t[q].c, 0, sizeof t[q].c);
	for(int i = 0;i <= t[q << 1].sz && i <= 20;i ++) {
		for(int j = 0;i+j <= 20 && j <= t[q << 1|1].sz;j ++) {
			t[q].c[i+j] = (t[q].c[i+j] + t[q << 1].c[i] * t[q << 1|1].c[j] % P) % P;
		}
	}
}
//建树
void build(int q, int l, int r) {
	t[q].sz = (r - l + 1);
	if(l == r) {
		t[q].c[0] = 1;
		t[q].c[1] = (a[l]%P + P) % P;
		return ;
	} 
	int mid = l+r >> 1;
	build(q << 1, l, mid);
	build(q << 1|1, mid+1, r);
	update(q);
}
//加数的操作
void puad(int q, int x) {
	if(!q || !x) return ;
	int tmp[50];
	tmp[0] = 1;
	for(int i = 1; i <= 20 && i <= t[q].sz;i ++) tmp[i] = tmp[i-1] * x % P;
	for(int i = min((int)20, t[q].sz);i != 0;i --) { 
		for(int j = 0;j < i;j ++) {
			t[q].c[i] = (t[q].c[i] + t[q].c[j] * tmp[i-j] % P * C[t[q].sz - j][i-j] ) % P;
		}
	}
	t[q].ad = (t[q].ad + x) % P;
}
//取相反数的操作
void pure(int q){
	if(!q) return ;
	for(int i = 1;i <= 20 && i <= t[q].sz;i ++) {
		if(i % 2) t[q].c[i] = P - t[q].c[i];
		else continue;
	}
	t[q].f ^= 1;
	t[q].ad = P - t[q].ad;
}
//下穿标记
void pushdown(int q) {
	if(t[q].f) {
		pure(q << 1);
		pure(q << 1|1);
		t[q].f = 0;
	} 
	if(t[q].ad) {
		puad(q << 1, t[q].ad);
		puad(q << 1|1, t[q].ad);
		t[q].ad = 0;
	}
}
//加一个数
void add(int q, int stl, int str, int l, int r, int x) {
	if(stl > r || str < l) return;
	if(stl >= l && str <= r) {
		puad(q, x);
		return ;
	}
	pushdown(q);
	int mid = str + stl >> 1;
	add(q<<1, stl, mid, l, r, x);
	add(q<<1|1, mid+1, str, l, r, x);
	update(q);
}
//区间取相反数
void rev(int q, int stl, int str, int l, int r) {
	if(stl > r || str < l) return;
	if(stl >= l && str <= r) {
		pure(q);
		return ;
	}
	pushdown(q);
	int mid = str + stl >> 1;
	rev(q<<1, stl, mid, l, r);
	rev(q<<1|1, mid+1, str, l, r);
	update(q);
}
//合并两个区间
node merge(node a, node b) {
	node e;
	e.sz = a.sz + b.sz;
	memset(e.c, 0, sizeof e.c);
	for(int i = 0;i <= (int)20 && i <= a.sz;i ++) {
		for(int j = 0;j <= b.sz && i+j <= (int)20;j ++) {
			e.c[i+j] = (e.c[i+j] + a.c[i] * b.c[j] % P) % P;
		} 
	}
	return e;
}
//查询操作
node query(int q, int stl, int str, int l, int r) {
	if(stl >= l && str <= r) {
		return t[q];
	}
	pushdown(q);
	int mid = stl+ str >> 1;
	if(r <= mid) return query(q << 1, stl, mid, l, r);
	else if(l > mid) return query(q << 1|1, mid+1, str, l, r);
	else return merge(query(q << 1, stl, mid, l, r), query(q << 1|1, mid+1, str, l, r));
}

signed main() {
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) {
		cin >> a[i];
	}
	init();
	build(1, 1, n);
	while(m --) {
		char op;
		cin >> op;
		if(op == 'I') {
			int a, b, c;
			cin >> a >> b >> c;
			add(1, 1, n, a, b, c);
		}
		if(op == 'R') {
			int a, b;
			cin >> a >> b;
			rev(1, 1, n, a, b);
		}
		if(op == 'Q') {
			int a, b, c;
			cin >> a >> b >> c;
			node e = query(1, 1, n, a, b);
			if(e.c[c] < 0) cout << P - e.c[c] << endl;
			else cout << e.c[c] % P << endl;
		}
	}
	
	return 0;
}