#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
using namespace std;
struct IO {
	char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
	~IO() { flush(); }
	char nc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 23, stdin), p1 == p2) ? EOF : *p1++; }
	template <typename T = int>
	T read() {
		char ch = nc();
		T sum = 0;
		while (ch < '0' || ch > '9') ch = nc();
		while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = nc();
		return sum;
    }
    void readStr(char str[]) {
    	int p = 0;
    	char ch = nc();
    	while (ch < '0' || ch > '1') ch = nc();
    	while (ch >= '0' && ch <= '1') str[p++] = ch, ch = nc();
	}
	void flush() { fwrite(obuf, O - obuf, 1, stdout); }
	void pc(char c) { (O - obuf < (1 << 23)) ? (*O++ = c) : (flush(), O = obuf, *O++ = c); }
	template <typename T>
	void print(T x) {
		if (x > 9) print(x / 10);
		pc(x % 10 + '0');
	}
} IO;
const int mod = 998244353;
inline int Mod(int x) { return x + ((x >> 31) & mod); }
inline int add(int x, int y) { return Mod(x + y - mod); }
inline int sub(int x, int y) { return Mod(x - y); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int sqr(int x) { return 1ll * x * x % mod; }
const int maxn = 100000, maxq = 1000000, K = 20;
char str[maxn + 5];
int v[maxn + 5];
struct query { int l, r, k; } q[maxq + 5];
vector<int> qL[2 * maxn + 5];
void st(int p, int l, int r, int x, int y, int id) {
	int mid = (l + r) / 2;
	if (x <= mid && mid < y) return qL[p].PB(id), void();
	if (y <= mid) st(p << 1, l, mid, x, y, id);
	if (mid < x) st(p << 1 | 1, mid + 1, r, x, y, id);
}
int ans[maxq + 5];
int f[maxn + 5][2 * K + 5][2], fl[maxn + 5][2 * K + 5][2], fr[maxn + 5][2 * K + 5][2], flr[maxn + 5][2 * K + 5][2];
inline void upd(int& x, int y) { x = add(x, y); }
void solve(int p, int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	memset(f[mid], 0, sizeof(f[mid]));
	memset(fl[mid], 0, sizeof(fl[mid]));
	memset(fr[mid], 0, sizeof(fr[mid]));
	memset(flr[mid], 0, sizeof(flr[mid]));
	f[mid][1][v[mid]] = 1;
	fl[mid][1][v[mid]] = fr[mid][1][v[mid]] = mid;
	flr[mid][1][v[mid]] = sqr(mid);
	for (int i = mid - 1; i >= l; i--) {
		memcpy(f[i], f[i + 1], sizeof(f[i]));
		memcpy(fl[i], fl[i + 1], sizeof(f[i])), memcpy(fr[i], fr[i + 1], sizeof(f[i]));
		memcpy(flr[i], flr[i + 1], sizeof(f[i]));
		for (int j = 0; j < 2 * K; j++) {
			int s = (j ^ v[i]) & 1;
			upd(f[i][j + 1][s], f[i + 1][j][s]);
			upd(fr[i][j + 1][s], fr[i + 1][j][s]);
			upd(fl[i][j + 1][s], mul(f[i + 1][j][s], i));
			upd(flr[i][j + 1][s], mul(fr[i + 1][j][s], i));
		}
		int s = v[i];
		upd(f[i][1][s], 1);
		upd(fl[i][1][s], i), upd(fr[i][1][s], i);
		upd(flr[i][1][s], sqr(i));
	}
	memset(f[mid + 1], 0, sizeof(f[mid + 1]));
	memset(fl[mid + 1], 0, sizeof(fl[mid + 1]));
	memset(fr[mid + 1], 0, sizeof(fr[mid + 1]));
	memset(flr[mid + 1], 0, sizeof(flr[mid + 1]));
	f[mid + 1][1][v[mid + 1]] = 1;
	fl[mid + 1][1][v[mid + 1]] = fr[mid + 1][1][v[mid + 1]] = mid + 1;
	flr[mid + 1][1][v[mid + 1]] = sqr(mid + 1); 
	for (int i = mid + 2; i <= r; i++) {
		memcpy(f[i], f[i - 1], sizeof(f[i]));
		memcpy(fl[i], fl[i - 1], sizeof(f[i])), memcpy(fr[i], fr[i - 1], sizeof(f[i]));
		memcpy(flr[i], flr[i - 1], sizeof(f[i]));
		for (int j = 0; j < 2 * K; j++) {
			int s = (j ^ v[i]) & 1;
			upd(f[i][j + 1][s], f[i - 1][j][s]);
			upd(fl[i][j + 1][s], fl[i - 1][j][s]);
			upd(fr[i][j + 1][s], mul(f[i - 1][j][s], i));
			upd(flr[i][j + 1][s], mul(fl[i - 1][j][s], i));
		}
		int s = v[i];
		upd(f[i][1][s], 1);
		upd(fl[i][1][s], i), upd(fr[i][1][s], i);
		upd(flr[i][1][s], sqr(i));
	}
	for (int id : qL[p]) {
		int l = q[id].l, r = q[id].r, k = q[id].k;
		upd(ans[id], sub(add(mul(fl[l][2 * k][1], r + 1), mul(fr[l][2 * k][1], l - 1)), add(mul(f[l][2 * k][1], mul(l - 1, r + 1)), flr[l][2 * k][1])));
		upd(ans[id], sub(add(mul(fl[r][2 * k][0], r + 1), mul(fr[r][2 * k][0], l - 1)), add(mul(f[r][2 * k][0], mul(l - 1, r + 1)), flr[r][2 * k][0])));
		for (int i = 1; i < 2 * k; i++) {
			int s1 = ~i & 1, s2 = i & 1;
			upd(ans[id], sub(add(mul(mul(fl[l][i][s1], f[r][2 * k - i][s2]), r + 1), mul(mul(f[l][i][s1], fr[r][2 * k - i][s2]), l - 1)), add(mul(mul(f[l][i][s1], f[r][2 * k - i][s2]), mul(l - 1, r + 1)), mul(fl[l][i][s1], fr[r][2 * k - i][s2]))));
		}
	}
	solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r);
}
int main() {
	int n = IO.read(), Q = IO.read();
	IO.readStr(str + 1);
	for (int i = 1; i <= n; i++) v[i] = str[i] - '0';
	for (int i = 1; i <= Q; i++) {
		q[i].l = IO.read(), q[i].r = IO.read(), q[i].k = IO.read();
		if (q[i].l < q[i].r) st(1, 1, n, q[i].l, q[i].r, i);
	}
	solve(1, 1, n);
	for (int i = 1; i <= Q; i++) IO.print(ans[i]), IO.pc('\n');
}