#include
using namespace std;
#define _l (long long int)
const int maxc = 23; const int maxn = 50009; const int mod = 19940417;
struct dat { int a[maxc], t; inline dat() { memset(a, 0, sizeof(a)); a[0] = 1; t = 0; } inline int& operator[](const int& x) { return a[x]; } inline int operator[](const int& x) const { return a[x]; } void add(int); void rev(); };
struct seg { int l, r, rv, a; dat d; seg *ch[2]; inline void update(); inline void catTag(int ta, int tr) { if (tr) { a = (mod - a) % mod; d. rev(); rv ^= 1; } if (ta) { a = (a + ta) % mod; d. add(ta); } } void pushDown() { ch[0]-> catTag(a, rv); ch[1]-> catTag(a, rv); a = rv = 0; } };
int n, m, a[maxn], comb[maxn][maxc]; seg sbuf_arr[maxn * 3], *sbuf(sbuf_arr), *rt;
void preComb() { comb[0][0] = 1; for (int i = 1; i < maxn; ++ i) { comb[i][0] = 1; for (int j = 1; j < i && j <= 20; ++ j) comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod; if (i <= 20) comb[i][i] = 1; } }
dat mergeDat(const dat& a, const dat& b) { static dat r; memset(r. a, 0, sizeof(r. a)); for (int i = 0; i <= 20; ++ i) for (int j = 0; i + j <= 20; ++ j) r[i + j] = (r[i + j] + _l a[i] * b[j]) % mod; r. t = a. t + b. t; r[0] = 1; return r; } void dat :: rev() { for (int i = 1; i < 20; i += 2) a[i] = (mod - a[i]) % mod; } void dat :: add(int v) { static int b[maxc], pv[maxc]; memset(b, 0, sizeof(b)); pv[0] = 1; for (int i = 1; i <= 20; ++ i) pv[i] = _l pv[i - 1] * v % mod; for (int i = 0; i <= 20; ++ i) for (int j = 0; j <= i && j <= t; ++ j) b[i] = (b[i] + _l a[j] * pv[i - j] % mod * comb[t - j][i - j]) % mod; memcpy(a, b, sizeof(a)); }
inline void seg :: update() { d = mergeDat(ch[0]-> d, ch[1]-> d); if (a) d. add(a); if (rv) d. rev(); }
#define midp(p) ((p->l+p->r)»1) inline seg* sgtBuild(int l, int r) { seg p(sbuf ++); p-> l = l, p-> r = r; p-> rv = 0, p-> a = 0; if (p-> l + 1 < p-> r) { p-> ch[0] = sgtBuild(l, midp(p)); p-> ch[1] = sgtBuild(midp(p), r); p-> d = mergeDat(p-> ch[0]-> d, p-> ch[1]-> d); } else { p-> d[1] = a[l]; p-> d. t = 1; } return p; } inline void sgtChg(seg p, int l, int r, int ta, int tr) { if (p-> l == l && p-> r == r) { p-> catTag(ta, tr); } else { p-> pushDown(); if (r <= midp(p)) sgtChg(p-> ch[0], l, r, ta, tr); else if (l >= midp(p)) sgtChg(p-> ch[1], l, r, ta, tr); else sgtChg(p-> ch[0], l, midp(p), ta, tr), sgtChg(p-> ch[1], midp(p), r, ta, tr); p-> update(); } } inline dat sgtQry(seg* p, int l, int r) { if (p-> l == l && p-> r == r) return p-> d; else { p-> pushDown(); dat ret; if (r <= midp(p)) ret = sgtQry(p-> ch[0], l, r); else if (l >= midp(p)) ret = sgtQry(p-> ch[1], l, r); else ret = mergeDat(sgtQry(p-> ch[0], l, midp(p)), sgtQry(p-> ch[1], midp(p), r)); if (p-> a) ret. add(p-> a); if (p-> rv) ret. rev(); return ret; } }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
preComb();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i)
scanf("%d", a + i);
rt = sgtBuild(1, n + 1);
while (m --) {
char opt[3];
int l, r, c;
scanf("%s%d%d", opt, &l, &r);
++ r;
if (opt[0] == 'I') {
scanf("%d", &c);
sgtChg(rt, l, r, c, 0);
}
else if (opt[0] == 'R') {
sgtChg(rt, l, r, 0, 1);
}
else {
scanf("%d", &c);
dat g(sgtQry(rt, l, r));
printf("%d\n", g[c]);
}
}
}