#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;

template<class A, class B> string to_string(const pair<A, B> &p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(const A &v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(const pair<A, B> &p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if (0) puts("No effect.")
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

using Info = pair<ll, ll>;
Info operator +(Info a, Info b) { return {a.first + b.first, a.second + b.second}; }

void InfoApply(Info &a, int l, int r, int x) {
	assert(x == 1);
	a.first = 1ll * (l + r) * (r - l + 1) / 2 - a.first;
	a.second = r - l + 1 - a.second;
}
void TagApply(int &a, int l, int r, int b) {
	assert(b == 1);
	a ^= 1;
}

/**
 * Author: Yuhao Yao
 * Date: 22-11-23
 * Description: Segment tree with lazy propogation.
 * Usage: Always define functions \textbf{InfoApply} and \textbf{TagApply} to tell segment tree how you apply modification.
 *  Combine is set as plus so if you just let T be numerical type then you have range sum in the info and as range query result. To have something different, say rangeMin, define a struct with constructer and + operation.
 * Time: O(\log N) per operation.
 * Status: tested on https://codeforces.com/gym/103371/problem/M.
 */
template<class Info, class Tag> class LazySegTree {
	#define ls i * 2
	#define rs i * 2 + 1

	int n;
	vector<Info> info;
	vector<Tag> tag;
public:
	LazySegTree(const vector<Info> &init): n(sz(init)) {
		assert(n > 0);
		info.resize(4 << __lg(n));
		tag.resize(4 << __lg(n));
		auto build = [&](auto &dfs, int i, int l, int r) {
			if (l == r) {
				info[i] = init[l];
				return;
			}
			int mid = (l + r) >> 1;
			dfs(dfs, ls, l, mid);
			dfs(dfs, rs, mid + 1, r);
			pull(i);
		};
		build(build, 1, 0, n - 1);
	}
private:
	void pull(int i) { info[i] = info[ls] + info[rs]; }

	template<class... T>
	void apply(int i, int l, int r, const T&... val) {
		InfoApply(info[i], l, r, val...);
		TagApply(tag[i], l, r, val...);
	}

	void push(int i, int l, int r) {
		if (tag[i] == Tag{}) return;
		int mid = (l + r) >> 1;
		apply(ls, l, mid, tag[i]);
		apply(rs, mid + 1, r, tag[i]);
		tag[i] = {};
	}
public:
	template<class... T>
	void rangeApply(int ql, int qr, const T&... val) {
		auto dfs = [&](auto &dfs, int i, int l, int r) {
			if (qr < l || r < ql) return;
			if (ql <= l && r <= qr) {
				apply(i, l, r, val...);
				return;
			}
			push(i, l, r);
			int mid = (l + r) >> 1;
			dfs(dfs, ls, l, mid);
			dfs(dfs, rs, mid + 1, r);
			pull(i);
		};
		dfs(dfs, 1, 0, n - 1);
	}

	Info rangeAsk(int ql, int qr) {
		Info res{};
		auto dfs = [&](auto &dfs, int i, int l, int r) {
			if (qr < l || r < ql) return;
			if (ql <= l && r <= qr) {
				res = res + info[i];
				return;
			}
			push(i, l, r);
			int mid = (l + r) >> 1;
			dfs(dfs, ls, l, mid);
			dfs(dfs, rs, mid + 1, r);
		};
		dfs(dfs, 1, 0, n - 1);
		return res;
	}

	int findFirst(int ql, int qr, function<bool(Info, int, int)> func) {
		auto dfs = [&](auto &dfs, int i, int l, int r) {
			if (qr < l || r < ql || (ql <= l && r <= qr && func(info[i], l, r) == 0)) return -1;
			if (l == r) return l;

			push(i, l, r);
			int mid = (l + r) >> 1;
			int res = dfs(dfs, ls, l, mid);
			if (res != -1) return res;
			else return dfs(dfs, rs, mid + 1, r);
		};
		return dfs(dfs, 1, 0, n - 1);
	};

	int findLast(int ql, int qr, function<bool(Info, int, int)> func) {
		auto dfs = [&](auto &dfs, int i, int l, int r) {
			if (qr < l || r < ql || (ql <= l && r <= qr && func(info[i], l, r) == 0)) return -1;
			if (l == r) return l;

			push(i, l, r);
			int mid = (l + r) >> 1;
			int res = dfs(dfs, rs, mid + 1, r);
			if (res != -1) return res;
			else return dfs(dfs, ls, l, mid);
		};
		return dfs(dfs, 1, 0, n - 1);
	};

	#undef ls
	#undef rs
};

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int n, q; 
	while (cin >> n >> q) {
		string s; cin >> s;
		using Info = pair<ll, ll>;
		using Tag = int;
		vector<Info> init(n);
		rep(i, 0, n - 1) if (s[i] == '1') {
			init[i] = {i, 1};
		}
		LazySegTree<Info, Tag> seg(init);
		while (q--) {
			int l, r; cin >> l >> r;
			l--, r--;
			seg.rangeApply(l, r, 1);
			auto [sum, tot] = seg.rangeAsk(0, n - 1);
			ll ans = sum * 2 - 1ll * (tot - 1) * tot + tot;
			printf("%lld\n", ans % 998244353);
		}
	}
	return 0;
}