#include <bits/stdc++.h>
#define MAXN 4010
using namespace std;

int n, m, q, ck[MAXN], po2[MAXN];
string S, T;
int hpo[MAXN][2], hp[2] = {131, 13131}, hm[2] = {998244353, 1000000007};
int s[MAXN][MAXN];
unordered_map<long long, bool> mp;
const int mod = 998244353, i2 = (mod + 1) >> 1;

void Addc(long long &nowh0, long long &nowh1, int c) {
	nowh0 = (nowh0 * hp[0] + c) % hm[0];
	nowh1 = (nowh1 * hp[1] + c) % hm[1];
	return;
}

void dfs(const int p) {
	if (p >= n) {
		long long nowh0 = 0, nowh1 = 0;
		for (int i = 0, j = -1; i < n; ++i) {
			while (j < i) ++j, Addc(nowh0, nowh1, S[j]);
			while (j < n - 1) {
				long long newh0 = nowh0, newh1 = nowh1;
				Addc(newh0, newh1, S[j + 1]);
				if (mp[(newh0 << 30) | newh1]) ++j, nowh0 = newh0, nowh1 = newh1;
				else break;
			}
			++s[i][i], --s[i][j + 1];
			nowh0 = (nowh0 + 1ll * (hm[0] - hpo[j - i][0]) * S[i]) % hm[0];
			nowh1 = (nowh1 + 1ll * (hm[1] - hpo[j - i][1]) * S[i]) % hm[1];
		}
		return;
	}
	if (S[p] != '?') dfs(p + 1);
	else {
		S[p] = '0', dfs(p + 1);
		S[p] = '1', dfs(p + 1);
		S[p] = '?';
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> q >> S;
	T = "0", m = n << 3;
	for (int i = 1; i < m; ++i) T += T[i >> 1] ^ (i & 1);
	hpo[0][0] = hpo[0][1] = 1;
	for (int i = 1; i < m; ++i) {
		hpo[i][0] = 1ll * hpo[i - 1][0] * hp[0] % hm[0];
		hpo[i][1] = 1ll * hpo[i - 1][1] * hp[1] % hm[1];
	}
	for (int i = 0; i < n; ++i) ck[i] = S[i] == '?';
	for (int i = 1; i < n; ++i) ck[i] += ck[i - 1];
	po2[0] = 1;
	for (int i = 1; i <= n; ++i) po2[i] = 1ll * po2[i - 1] * i2 % mod;
	for (int i = 0; i < m; ++i) {
		long long nowh0 = 0, nowh1 = 0;
		for (int j = i; j < m; ++j) {
			Addc(nowh0, nowh1, T[j]);
			mp[(nowh0 << 30) | nowh1] = 1;
		}
	}
	dfs(0);
	for (int i = 0; i < n; ++i) for (int j = 1; j < n; ++j) s[i][j] += s[i][j - 1];
	for (int i = 0; i < n; ++i) for (int j = 1; j < n; ++j) s[i][j] = (s[i][j] + s[i][j - 1]) % mod;
	for (int i = 1; i < n; ++i) for (int j = 0; j < n; ++j) s[i][j] = (s[i][j] + s[i - 1][j]) % mod;
	while (q--) {
		int l, r; cin >> l >> r;
		int ans = s[n - 1][r], cc = ck[r];
		if (l) ans = (ans + mod - s[l - 1][r]) % mod, cc -= ck[l - 1];
		cout << 1ll * ans * po2[ck[n - 1] - cc] % mod << "\n";
	}
	return 0;
}