#include #include using namespace std; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i using mint = atcoder::modint998244353; // Disjoint sparse table // https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404 // https://drken1215.hatenablog.com/entry/2018/09/08/162600 // Complexity: O(NlogN) for precalculation, O(1) per query // - get(l, r): return op(x_l, ..., x_{r - 1}) template struct disj_sparse_table { int N, sz; std::vector> d; static int _msb(int x) noexcept { return x == 0 ? 0 : (__builtin_clz(x) ^ 31); } disj_sparse_table() = default; disj_sparse_table(const std::vector &seq) : N(seq.size()) { sz = 1 << (_msb(N - 1) + 1); d.assign(_msb(sz) + 1, std::vector(sz)); std::copy(seq.begin(), seq.end(), d[0].begin()); for (int h = 1, half = 2; half < N; ++h, half <<= 1) { for (int i = half; i < sz; i += half * 2) { d[h][i - 1] = d[0][i - 1]; for (int j = i - 2; j >= i - half; --j) d[h][j] = op(d[0][j], d[h][j + 1]); d[h][i] = d[0][i]; for (int j = i + 1; j < i + half; ++j) d[h][j] = op(d[h][j - 1], d[0][j]); } } } // [l, r), 0-indexed S prod(int l, int r) const { assert(l >= 0 and r <= N and l < r); if (l + 1 == r) return d[0][l]; int h = _msb(l ^ (r - 1)); return op(d[h][l], d[h][r - 1]); } }; using S = vector; S op(S l, S r) { S ret(max(l.size() + r.size() - 1, 0)); REP(i, l.size()) REP(j, r.size()) ret.at(i + j) += l.at(i) * r.at(j); return ret; } int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector init(N); for (int i = 0; i < N; ++i) { int p; cin >> p; init.at(i) = {1, p}; } disj_sparse_table dst(init); int Q; cin >> Q; while (Q--) { int l, r, k; cin >> l >> r >> k; --l; mint ret = 0; if (l + 1 == r) { ret = dst.d[0][l][k]; } else { const int h = dst._msb(l ^ (r - 1)); REP(kl, k + 1) { if (kl < (int)dst.d.at(h).at(l).size() and k - kl < (int)dst.d.at(h).at(r - 1).size()) ret += dst.d.at(h).at(l).at(kl) * dst.d.at(h).at(r - 1).at(k - kl); } } cout << ret.val() << '\n'; } }