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

int n, m, q;
string S, T;
int ans;

void dfs(const int p, const int l, const int r) {
	if (p > r) {
		for (int lp = l; lp <= r; ++lp) for (int rp = lp; rp <= r; ++rp) {
			int len = rp - lp + 1;
			string tmp = S.substr(lp, len);
			bool flag = 0;
			for (int i = 0; i <= m - len; ++i) if (tmp == T.substr(i, len)) {flag = 1; break;}
			ans += flag;
		}
		return;
	}
	if (S[p] != '?') dfs(p + 1, l, r);
	else {
		S[p] = '0', dfs(p + 1, l, r);
		S[p] = '1', dfs(p + 1, l, r);
		S[p] = '?';
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> q >> S;
	T = "0", m = n << 2;
	for (int i = 1; i < m; ++i) T += T[i >> 1] ^ (i & 1);
	while (q--) {
		int l, r; cin >> l >> r;
		ans = 0;
		dfs(l, l, r);
		cout << ans << "\n";
	}
	return 0;
}