#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<ll, ll, ll> tlll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '0');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define N 300007

struct node {
	int cnt0, cnt1;
	ll sum0, sum1;
	inline node operator + (const node &obj) {
		node ret;
		ret.cnt0 = cnt0 + obj.cnt0;
		ret.cnt1 = cnt1 + obj.cnt1;
		ret.sum0 = sum0 + obj.sum0;
		ret.sum1 = sum1 + obj.sum1;
		return ret;
	}
	inline void rev() {
		swap(cnt0, cnt1);
		swap(sum0, sum1);
	}
} c[N << 2];

char s[N];

bool tag[N << 2];

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) / 2)

inline void pushdown(int rt) {
	if (tag[rt]) {
		tag[rt] = 0;
		c[ls].rev(); tag[ls] ^= 1;
		c[rs].rev(); tag[rs] ^= 1;
	}
}

void build(int rt, int l, int r) {
	tag[rt] = 0; 
	if (l == r) {
		if (s[l] == '1') c[rt] = {0, 1, 0, l};
		else c[rt] = {1, 0, l, 0};
		return;
	}
	build(ls, l, mid);
	build(rs, mid + 1, r);
	c[rt] = c[ls] + c[rs];
}

void rev(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		c[rt].rev(); tag[rt] ^= 1; return;
	}
	pushdown(rt);
	if (L <= mid) rev(ls, l, mid, L, R);
	if (R > mid) rev(rs, mid + 1, r, L, R);
	c[rt] = c[ls] + c[rs];
}

ll qsum0(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) return c[rt].sum0;
	pushdown(rt);
	ll ret = 0;
	if (L <= mid) ret += qsum0(ls, l, mid, L, R);
	if (R > mid) ret += qsum0(rs, mid + 1, r, L, R);
	return ret;
}

ll qsum1(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) return c[rt].sum1;
	pushdown(rt);
	ll ret = 0;
	if (L <= mid) ret += qsum1(ls, l, mid, L, R);
	if (R > mid) ret += qsum1(rs, mid + 1, r, L, R);
	return ret;
}

node qpos(int rt, int l, int r, int p) {
	if (l == r) return c[rt];
	pushdown(rt);
	return p <= mid ? qpos(ls, l, mid, p) : qpos(rs, mid + 1, r, p);
}

int main() {
	int n, q;
	while (scanf("%d%d", &n, &q) != EOF) {
		scanf("%s", s + 1);
		build(1, 1, n);
		rep(i, 1, q) {
			int l = rd(), r = rd();
			rev(1, 1, n, l, r);
			int tot = c[1].cnt1;
			if (tot == 0) {puts("0"); continue;}
			if (tot == n) {printf("%d\n", n); continue;}
			ll res = qsum1(1, 1, n, tot + 1, n);
			if (tot > 1) res -= qsum0(1, 1, n, 1, tot - 1);
			res *= 2;
			auto cur = qpos(1, 1, n, tot);
			cur.cnt1 == 1 ? res += tot : res -= tot;
			printf("%lld\n", res % 998244353);
		}
	}
	return 0;	
}