#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<iomanip>
#include<cmath>
#include<stack>

using namespace std;
using ll=long long;
using P=pair<ll,ll>;

const int N=3e5+5;
const int mod=998244353;
ll z[N<<2],o[N<<2],g[N<<2];
ll zs[N<<2],os[N<<2];

string s;

void pushup(int k){
	z[k]=z[k<<1]+z[k<<1|1];
	o[k]=o[k<<1]+o[k<<1|1];
	zs[k]=zs[k<<1]+zs[k<<1|1];
	os[k]=os[k<<1]+os[k<<1|1];
}
void pushdown(int k){
	if(g[k]){
		swap(o[k<<1],z[k<<1]);
		swap(o[k<<1|1],z[k<<1|1]);
		swap(zs[k<<1],os[k<<1]);
		swap(zs[k<<1|1],os[k<<1|1]);
		g[k<<1]^=1,g[k<<1|1]^=1;
		g[k]=0;
	}
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		z[k]=s[l]=='0';
		o[k]=s[l]=='1';
		zs[k]=(s[l]=='0')*l;
		os[k]=(s[l]=='1')*l;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(int k,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)
	{
		swap(z[k],o[k]);
		swap(zs[k],os[k]);
		g[k]^=1;
		return;	
	}
	int mid=l+r>>1; pushdown(k);
	if(ql<=mid)update(k<<1,l,mid,ql,qr);
	if(mid<qr)update(k<<1|1,mid+1,r,ql,qr);
	pushup(k);
}
ll getp(int k,int l,int r,int w){
	if(l==r)return l;
	int mid=l+r>>1; pushdown(k);
	if(o[k<<1]>=w)return getp(k<<1,l,mid,w);
	else return getp(k<<1|1,mid+1,r,w-o[k<<1]);
}
ll qy0(int k,int l,int r,int ql,int qr,int w){
	if(ql<=l&&r<=qr)return !w?z[k]:zs[k];
	int mid=l+r>>1; ll ans=0; pushdown(k); 
	if(ql<=mid)ans+=qy0(k<<1,l,mid,ql,qr,w);
	if(mid<qr)ans+=qy0(k<<1|1,mid+1,r,ql,qr,w);
	return ans;
}
ll qy1(int k,int l,int r,int ql,int qr,int w){
	if(ql<=l&&r<=qr)return !w?o[k]:os[k];
	int mid=l+r>>1; ll ans=0; pushdown(k);
	if(ql<=mid)ans+=qy1(k<<1,l,mid,ql,qr,w);
	if(mid<qr)ans+=qy1(k<<1|1,mid+1,r,ql,qr,w);
	return ans;
}

void solve()
{
	int n,q;
	while(cin>>n>>q&&n!=0)
	{
		memset(o,0,sizeof(ll)*(n*4+5));
		memset(z,0,sizeof(ll)*(n*4+5));
		memset(os,0,sizeof(ll)*(n*4+5));
		memset(zs,0,sizeof(ll)*(n*4+5));
		cin>>s; s=' '+s;
		build(1,1,n);
		for(int i=1,l,r;i<=q;i++)
		{
			cin>>l>>r;
			update(1,1,n,l,r);
			int k=qy1(1,1,n,1,n,0);
			ll ans=k+2*(qy1(1,1,n,k+1,n,1)-qy0(1,1,n,1,k,1));
			cout<<(ans%mod+mod)%mod<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1; //cin>>t;
	while(t--)solve();
	return 0;
}