#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>

using namespace std;

const int maxn=5e5; 
const int mod=998244353; 
int n,q;
int add(int x,int y) {
	return (x+=y)>=mod?x-mod:x; 
}
int s0[maxn*4+5],s1[maxn*4+5],cnt[maxn*4+5],len[maxn*4+5],tag[maxn*4+5];
char s[maxn+5];  
void upd(int p) {
	s0[p]=add(s0[p+p],s0[p+p+1]); 
	s1[p]=add(s1[p+p],s1[p+p+1]); 
	cnt[p]=add(cnt[p+p],cnt[p+p+1]); 
}
void seta(int p) {
	swap(s0[p],s1[p]);
	cnt[p]=len[p]-cnt[p];
	tag[p]^=1; 
}
void push(int p) {
	if (tag[p]==0) return ;
	seta(p+p);
	seta(p+p+1);
	tag[p]=0; 
}
void build(int p,int l,int r) {
	len[p]=r-l+1; 
	tag[p]=0; 
	if (l==r) {
		if (s[l]=='1') s1[p]=l,s0[p]=0,cnt[p]=1; 
		else s0[p]=l,s1[p]=0,cnt[p]=0; 
		return; 
	}
	int mid=(l+r)>>1;
	build(p+p,l,mid);
	build(p+p+1,mid+1,r);
	upd(p); 
}
void modify(int p,int l,int r,int ql,int qr) {
	if (l==ql&&r==qr) {
		seta(p);
		return ; 
	}
	push(p); 
	int mid=(l+r)>>1;
	if (qr<=mid) modify(p+p,l,mid,ql,qr);
	else if (mid<ql) modify(p+p+1,mid+1,r,ql,qr);
	else modify(p+p,l,mid,ql,mid),modify(p+p+1,mid+1,r,mid+1,qr);
	upd(p); 
}
pair <int,pii> operator + (const pair<int,pii> &x,const pair<int,pii> &y) {
	return {add(x.fi,y.fi),{add(x.se.fi,y.se.fi),add(x.se.se,y.se.se)}};
}
pair <int, pii> query(int p,int l,int r,int ql,int qr){
	if (ql>qr) return {0,{0,0}}; 
	if (l==ql&&r==qr) return {cnt[p],{s0[p],s1[p]}}; 
	push(p); 
	int mid=(l+r)>>1;
	if (qr<=mid) return query(p+p,l,mid,ql,qr);
	else if (mid<ql) return query(p+p+1,mid+1,r,ql,qr);
	else return query(p+p,l,mid,ql,mid)+query(p+p+1,mid+1,r,mid+1,qr);
} 
int main() {
	while (cin>>n>>q) 
	{
		scanf("%s",s+1);
		build(1,1,n); 
		for (int i=1;i<=q;i++) {
			int l,r; 
			scanf("%d %d",&l,&r);
			modify(1,1,n,l,r);
			pair<int,pii> t=query(1,1,n,1,n); 
			int k=t.fi;
			if (k==0) {
				puts("0");
				continue ; 
			}
			t=query(1,1,n,k,n); 
			int S1=t.se.se; 
			t=query(1,1,n,1,k-1); 
			int S0=t.se.fi; 
			int ans=2ll*add(S1,mod-S0)%mod; 
			ans=add(ans,mod-k);
			printf("%d\n",ans); 
		}
	}
	return 0;
}