rt，样例过了但是全 WA。

record

#include <iostream>

using namespace std;
using LL = long long;

const int kN = 5e4 + 1, kC = 21;
const LL kM = 19940417;

struct T {
  bool n;
  LL a;

  T(bool n = 0, LL a = 0) : n(n), a((a % kM + kM) % kM) {}
  const T operator+=(const T &o) {
    if (o.n) {
      n ^= 1, a = (kM - a) % kM;
    }
    a = (a + o.a) % kM;
    return *this;
  }
};
LL _c[kN][kC];
LL C(int n, int m) {
  if (m < 0 || m > n) {
    return 0;
  }
  if (_c[n][m]) {
    return _c[n][m];
  }
  if (m == 0 || m == n) {
    return _c[n][m] = 1;
  }
  return _c[n][m] = (C(n - 1, m - 1) + C(n - 1, m)) % kM;
}
struct I {
  LL c[kC];
  int n;

  I() { fill(c, c + kC, 0), c[n = 0] = 1; }
  const I operator+(const I &o) const {
    I s;
    s.n = n + o.n, s.c[0] = 0;
    for (int i = 0; i < kC && i <= n; ++i) {
      for (int j = 0; i + j < kC && j <= o.n; ++j) {
        s.c[i + j] = (s.c[i + j] + c[i] * o.c[j] % kM) % kM;
      }
    }
    return s;
  }
  const I operator+=(const T &o) {
    if (o.n) {
      for (int i = 1; i < kC && i <= n; i += 2) {
        c[i] = (kM - c[i]) % kM;
      }
    }
    LL _c[kC], px[kC];
    copy(c, c + kC, _c);
    for (int i = px[0] = 1; i < kC && i <= n; ++i) {
      px[i] = px[i - 1] * o.a % kM;
    }
    for (int i = 1; i < kC && i <= n; ++i) {
      c[i] = 0;
      for (int j = 0; j <= i; ++j) {
        c[i] = (c[i] + _c[j] * px[i - j] % kM * C(n - j, i - j) % kM) % kM;
      }
    }
    return *this;
  }
};
struct E {
  I v;
  T t;
  int l, r;
} e[kN << 2];
void B(int x, int l, int r) {
  e[x].l = l, e[x].r = r;
  if (l == r) {
    LL v;
    cin >> v;
    e[x].v.n = 1, e[x].v += T(0, v);
    return;
  }
  int m = l + r >> 1;
  B(x * 2, l, m), B(x * 2 + 1, m + 1, r);
  e[x].v = e[x * 2].v + e[x * 2 + 1].v;
}
void U(int x, int l, int r, T t) {
  if (e[x].l == l && e[x].r == r) {
    e[x].v += t, e[x].t += t;
    return;
  }
  e[x * 2].v += e[x].t, e[x * 2 + 1].v += e[x].t, e[x].t = T();
  if (l <= e[x * 2].r) {
    U(x * 2, l, min(r, e[x * 2].r), t);
  }
  if (e[x * 2 + 1].l <= r) {
    U(x * 2 + 1, max(l, e[x * 2 + 1].l), r, t);
  }
  e[x].v = e[x * 2].v + e[x * 2 + 1].v;
}
I Q(int x, int l, int r) {
  if (e[x].l == l && e[x].r == r) {
    return e[x].v;
  }
  e[x * 2].v += e[x].t, e[x * 2 + 1].v += e[x].t, e[x].t = T();
  I s;
  if (l <= e[x * 2].r) {
    s = s + Q(x * 2, l, min(r, e[x * 2].r));
  }
  if (e[x * 2 + 1].l <= r) {
    s = s + Q(x * 2 + 1, max(l, e[x * 2 + 1].l), r);
  }
  e[x].v = e[x * 2].v + e[x * 2 + 1].v;
  return s;
}

int n, q;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  B(1, 1, n);
  for (int l, r, v; q--;) {
    char o;
    cin >> o >> l >> r;
    if (o == 'I') {
      cin >> v;
      U(1, l, r, T(0, v));
    } else if (o == 'R') {
      U(1, l, r, T(1, 0));
    } else {
      cin >> v;
      I s = Q(1, l, r);
      cout << s.c[v] << '\n';
    }
  }
  return 0;
}