#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 50050
#define M 200200
#define mod 998244353
IL int read()
{
	reg int x=0; reg char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}

IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){long long r=1ll*x*y; return r<mod?r:r%mod;}

bool ok[16][N][2];
int n,q,p[N][2],ip[N][2];
char s[N];
int pre[N],pw[N],ipw[N];

IL bool chk(reg bool x,reg char c)
{
	if(c=='?')return 1;
	return x?c=='1':c=='0';
}

int wr[N],wl[N];

struct Segment
{
	
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (l[o]+r[o]>>1)

int l[N<<2],r[N<<2],val[N<<2],sum[N<<2],tag[N<<2];

void build(reg int o,reg int L,reg int R)
{
	l[o]=L,r[o]=R;
	if(L==R)val[o]=wl[L];
	else build(ls,L,mid),build(rs,mid+1,R),val[o]=Add(val[ls],val[rs]);
}

IL void pushup(reg int o){sum[o]=Add(sum[ls],sum[rs]);}
IL void apply(reg int o,reg int k){Pls(tag[o],k),Pls(sum[o],Mul(val[o],k));}
IL void pushdown(reg int o){if(tag[o])apply(ls,tag[o]),apply(rs,tag[o]),tag[o]=0;}

void modify(reg int o,reg int L,reg int R,reg int k)
{
	if(L<=l[o]&&r[o]<=R)return apply(o,k);
	if(L>r[o]||l[o]>R)return;
	pushdown(o),modify(ls,L,R,k),modify(rs,L,R,k),pushup(o);
}

int query(reg int o,reg int L,reg int R)
{
	if(L<=l[o]&&r[o]<=R)return sum[o];
	if(L>r[o]||l[o]>R)return 0;
	return pushdown(o),Add(query(ls,L,R),query(rs,L,R));
}

#undef ls
#undef rs
#undef mid
		
}A,B;

struct Opt{int l,r,w;};
struct Ques{int l,w,id;};
std::vector<Opt>vec[N];
std::vector<Ques>shelf[N];
int ans[N];

IL void slack(reg int lx,reg int rx,reg int ly,reg int ry,reg int w)
{
	if(lx>rx||ly>ry)return;
	vec[rx].push_back({ly,ry,w});
	if(lx>1)vec[lx-1].push_back({ly,ry,mod-w});
}

IL int min(reg int x,reg int y){return x<y?x:y;}

main()
{
	n=read(),q=read(),scanf("%s",s+1);
	pw[0]=ipw[0]=1;
	for(reg int i=1;i<=n;++i)pre[i]=pre[i-1]+(s[i]=='?');
	for(reg int i=1;i<=n;++i)pw[i]=Mul(pw[i-1],2),ipw[i]=Mul(ipw[i-1],mod+1>>1);
	for(reg int i=1;i<=n;++i)ok[0][i][0]=chk(0,s[i]),ok[0][i][1]=chk(1,s[i]);
	for(reg int o=1,i,j;o<16;++o)for(i=1;i+(1<<o)-1<=n;++i)for(j=2;j--;)
		ok[o][i][j]=ok[o-1][i][j]&&ok[o-1][i+(1<<o-1)][!j];
	for(reg int i=1,j,x,y,o;i<=n;++i)for(j=2;j--;)
	{
		x=i,y=j;
		for(o=16;o--;)if(x+(1<<o)-1<=n&&ok[o][x][y])y^=1,x+=1<<o;
		p[i][j]=x-i;
	}
	for(reg int i=1;i<=n;++i)ok[0][i][0]=chk(0,s[i]),ok[0][i][1]=chk(1,s[i]);
	for(reg int o=1,i,j;o<16;++o)for(i=n;i-(1<<o)+1>0;--i)for(j=2;j--;)
		ok[o][i][j]=ok[o-1][i][j]&&ok[o-1][i-(1<<o-1)][!j];
	for(reg int i=1,j,x,y,o;i<=n;++i)for(j=2;j--;)
	{
		x=i,y=j;
		for(o=16;o--;)if(x-(1<<o)+1>0&&ok[o][x][y])y^=1,x-=1<<o;
		ip[i][j]=i-x;
	}
	for(reg int i=1;i<=n;++i)wr[i]=pw[pre[n]-pre[i]],wl[i]=pw[pre[i-1]];
	for(reg int i=2,x,y;i<=n;++i)for(x=2;x--;)for(y=2;y--;)
		slack(i,i+p[i][x]-1,i-ip[i-1][y],i-1,1);
	for(reg int l=2,r,o,x,y;l<=n;++l)for(o=0;l+(1<<o)-1<n;++o)for(x=2;x--;)y=(o&1)^x,
		r=l+(1<<o)-1,slack(r+1,l+min(p[l][x],1<<o+1)-1,r-min(ip[r][y],1<<o+1)+1,l-1,mod-1);
	for(reg int i=1,l,r;i<=q;++i)
	{
		l=read()+1,r=read()+1,ans[i]=Mul(r-l+1,pw[pre[r]-pre[l-1]]);
		shelf[r].push_back({l,ipw[pre[l-1]+pre[n]-pre[r]],i});
	}
	for(reg int i=1;i<=n;++i)Pls(wr[i],wr[i-1]);
	A.build(1,1,n),B.build(1,1,n);
	for(reg int i=1;i<=n;++i)for(auto p:vec[i])
		A.modify(1,p.l,p.r,p.w);
	for(reg int i=1;i<=n;++i)
	{
		for(auto p:shelf[i])
		{
			Pls(ans[p.id],Mul(p.w,Mul(A.query(1,p.l,n),wr[i])));
			Pls(ans[p.id],Mul(p.w,B.query(1,p.l,n)));
		}
		for(auto p:vec[i])
		{
			A.modify(1,p.l,p.r,mod-p.w);
			B.modify(1,p.l,p.r,Mul(p.w,wr[i])); 
		}
	}
	for(reg int i=1;i<=q;++i)printf("%d\n",ans[i]);
}