#include <bits/stdc++.h>
using namespace std;

const int N=5e4+5;
const int M=2e5+5;
const int Mod=998244353;
const int inv2=(Mod+1)/2;

struct segment
{
	int l,r;
	long long val;
};

int sum[N], L0[N], L1[N], R0[N], R1[N], L[M], R[M];
vector <pair<int,int> > add[N], del[N], que[N];
vector <segment> Add00[N], Add01[N], Add10[N], Add11[N];
long long p2[N], invp2[N], preval[N], sufval[N], val[20][N];
long long c1[N], c2[N], ans[M], n;
long long c00[N], c01[N], c10[N], c11[N];
char s[N];

void update1(long long c[],int x,int y)
{
	for(int i=x;i;i-=i&-i)
		(c[i] += y) %= Mod;
}

long long query1(long long c[],int x)
{
	long long ans=0;
	for(int i=x;i<=n;i+=i&-i)
		(ans += c[i]) %= Mod;
	return ans;
}

void update2(long long c[],int x,long long y)
{
	for(int i=x;i<=n;i+=i&-i)
		(c[i] += y) %= Mod;
}

long long query2(long long c[],int x)
{
	long long ans=0;
	for(int i=x;i;i-=i&-i)
		(ans += c[i]) %= Mod;
	return ans;
}

int main()
{
	int m;
	cin >> n >> m;
	scanf("%s",s+1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&L[i],&R[i]);
		L[i]++, R[i]++;
		que[R[i]].push_back(make_pair(L[i],i));
	}

	for(int i=1;i<=n;i++)
	{
		if(s[i]=='0' || s[i]=='?')
			L0[i]=1;

		if(s[i]=='1' || s[i]=='?')
			L1[i]=1;

		if(L0[i])
		{
			for(int j=1;j*2<=i;j*=2)
				if(L1[i-j]>=j)
					L0[i]=j*2;
				else
					break;

			L0[i] += L1[i-L0[i]];
		}

		if(L1[i])
		{
			for(int j=1;j*2<=i;j*=2)
				if(L0[i-j]>=j)
					L1[i]=j*2;
				else
					break;

			L1[i] += L0[i-L1[i]];
		}
	}

	for(int i=n;i>=1;i--)
	{
		if(s[i]=='0' || s[i]=='?')
			R0[i]=1;

		if(s[i]=='1' || s[i]=='?')
			R1[i]=1;

		if(R0[i])
		{
			for(int j=1;j*2<=n-i+1;j*=2)
				if(R1[i+j]>=j)
					R0[i]=j*2;
				else
					break;

			R0[i] += R1[i+R0[i]];
		}

		if(R1[i])
		{
			for(int j=1;j*2<=n-i+1;j*=2)
				if(R0[i+j]>=j)
					R1[i]=j*2;
				else
					break;

			R1[i] += R0[i+R1[i]];
		}
	}

	p2[0]=invp2[0]=1;
	for(int i=1;i<=n;i++)
	{
		p2[i]=p2[i-1]*2%Mod;
		invp2[i]=invp2[i-1]*inv2%Mod;
	}

	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+(s[i]=='?');

	for(int i=n;i>=1;i--)
		sufval[i]=(sufval[i+1]+invp2[sum[n]-sum[i-1]])%Mod;

	for(int i=1;i<=n;i++)
		preval[i]=(preval[i-1]+invp2[sum[i]])%Mod;

	for(int i=0;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			val[i][j]=(val[i][j-1]+sufval[j]*preval[j+(1<<i)-1])%Mod;

	for(int i=1;i<=n;i++)
		val[19][i]=(val[19][i-1]+sufval[i]*preval[i-1])%Mod;

	for(int i=1;i<=n;i++)
	{
		add[i].push_back(make_pair(i,-2));
		del[i+R0[i]-1].push_back(make_pair(i,-2));
		add[i].push_back(make_pair(i,-2));
		del[i+R1[i]-1].push_back(make_pair(i,-2));
	}

	for(int k=0;(1<<k)<=n;k++)
		for(int i=1;i+(1<<k)-1<=n;i++)
		{
			int cnt=min(max(0,R0[i]-(1<<k)),(1<<k));
			add[i+(1<<k)-1].push_back(make_pair(i,1));
			del[i+(1<<k)-1+cnt].push_back(make_pair(i,1));

			cnt=min(max(0,R1[i]-(1<<k)),(1<<k));
			add[i+(1<<k)-1].push_back(make_pair(i,1));
			del[i+(1<<k)-1+cnt].push_back(make_pair(i,1));
		}

	for(int i=0;i<=n;i++)
	{
		for(auto x:add[i])
			update1(c1,x.first,sufval[x.first]*x.second);

		for(auto x:del[i])
		{
			update1(c1,x.first,-sufval[x.first]*x.second);
			update1(c2,x.first,sufval[x.first]*preval[i]*x.second%Mod);
		}

		for(auto x:que[i])
			(ans[x.second] += query1(c1,x.first)*preval[i]+query1(c2,x.first)) %= Mod;
	}

	memset(c1,0,sizeof(c1));
	memset(c2,0,sizeof(c2));
	for(int i=0;i<=n+1;i++)
		add[i].clear(), del[i].clear(), que[i].clear();

	for(int i=1;i<=n;i++)
	{
		add[i].push_back(make_pair(i,-2*preval[i-1]));
		del[i-L0[i-1]].push_back(make_pair(i,-2*preval[i-1]));
		add[i].push_back(make_pair(i,-2*preval[i-1]));
		del[i-L1[i-1]].push_back(make_pair(i,-2*preval[i-1]));
	}

	for(int i=1;i<=m;i++)
		que[L[i]].push_back(make_pair(R[i],i));

	for(int k=0;(1<<k)<=n;k++)
		for(int i=1;i+(1<<k)-1<=n;i++)
		{
			int cnt=min(max(0,L0[i+(1<<k)-1]-(1<<k)),(1<<k));
			add[i].push_back(make_pair(i+(1<<k)-1,preval[i+(1<<k)-1]));
			del[i-cnt].push_back(make_pair(i+(1<<k)-1,preval[i+(1<<k)-1]));

			cnt=min(max(0,L1[i+(1<<k)-1]-(1<<k)),(1<<k));
			add[i].push_back(make_pair(i+(1<<k)-1,preval[i+(1<<k)-1]));
			del[i-cnt].push_back(make_pair(i+(1<<k)-1,preval[i+(1<<k)-1]));
		}

	for(int i=n;i>=1;i--)
	{
		for(auto x:add[i])
			update2(c1,x.first,x.second);

		for(auto x:del[i])
		{
			update2(c1,x.first,-x.second);
			update2(c2,x.first,sufval[i]*x.second%Mod);
		}

		for(auto x:que[i])
			(ans[x.second] += query2(c1,x.first)*sufval[i]+query2(c2,x.first)) %= Mod;
	}

	for(int i=0;i<=n+1;i++)
		que[i].clear();

	for(int i=1;i<=n;i++)
	{
		Add00[i].push_back((segment){i-L0[i-1],i,1});
		Add01[i].push_back((segment){1,i-L0[i-1]-1,sufval[i-L0[i-1]]});
		Add00[i+R0[i]-1].push_back((segment){i-L0[i-1],i,-1});
		Add01[i+R0[i]-1].push_back((segment){1,i-L0[i-1]-1,-sufval[i-L0[i-1]]});
		Add10[i+R0[i]-1].push_back((segment){i-L0[i-1],i,preval[i+R0[i]-1]});
		Add11[i+R0[i]-1].push_back((segment){1,i-L0[i-1]-1,sufval[i-L0[i-1]]*preval[i+R0[i]-1]%Mod});

		Add00[i].push_back((segment){i-L1[i-1],i,1});
		Add01[i].push_back((segment){1,i-L1[i-1]-1,sufval[i-L1[i-1]]});
		Add00[i+R0[i]-1].push_back((segment){i-L1[i-1],i,-1});
		Add01[i+R0[i]-1].push_back((segment){1,i-L1[i-1]-1,-sufval[i-L1[i-1]]});
		Add10[i+R0[i]-1].push_back((segment){i-L1[i-1],i,preval[i+R0[i]-1]});
		Add11[i+R0[i]-1].push_back((segment){1,i-L1[i-1]-1,sufval[i-L1[i-1]]*preval[i+R0[i]-1]%Mod});

		Add00[i].push_back((segment){i-L0[i-1],i,1});
		Add01[i].push_back((segment){1,i-L0[i-1]-1,sufval[i-L0[i-1]]});
		Add00[i+R1[i]-1].push_back((segment){i-L0[i-1],i,-1});
		Add01[i+R1[i]-1].push_back((segment){1,i-L0[i-1]-1,-sufval[i-L0[i-1]]});
		Add10[i+R1[i]-1].push_back((segment){i-L0[i-1],i,preval[i+R1[i]-1]});
		Add11[i+R1[i]-1].push_back((segment){1,i-L0[i-1]-1,sufval[i-L0[i-1]]*preval[i+R1[i]-1]%Mod});

		Add00[i].push_back((segment){i-L1[i-1],i,1});
		Add01[i].push_back((segment){1,i-L1[i-1]-1,sufval[i-L1[i-1]]});
		Add00[i+R1[i]-1].push_back((segment){i-L1[i-1],i,-1});
		Add01[i+R1[i]-1].push_back((segment){1,i-L1[i-1]-1,-sufval[i-L1[i-1]]});
		Add10[i+R1[i]-1].push_back((segment){i-L1[i-1],i,preval[i+R1[i]-1]});
		Add11[i+R1[i]-1].push_back((segment){1,i-L1[i-1]-1,sufval[i-L1[i-1]]*preval[i+R1[i]-1]%Mod});
	}

	for(int k=0;(1<<k)<=n;k++)
		for(int i=1;i+(1<<k)-1<=n;i++)
		{
			if(k%2==0)
			{
				int cntl=max(min(L0[i+(1<<k)-1]-(1<<k),1<<k),0), cntr=max(min(R0[i]-(1<<k),1<<k),0);
				Add00[i+(1<<k)-1].push_back((segment){i-cntl,i,-1});
				Add01[i+(1<<k)-1].push_back((segment){1,i-cntl-1,-sufval[i-cntl]});
				Add00[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,1});
				Add01[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,sufval[i-cntl]});
				Add10[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,-preval[i+(1<<k)-1+cntr]});
				Add11[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,-sufval[i-cntl]*preval[i+(1<<k)-1+cntr]});

				cntl=max(min(L1[i+(1<<k)-1]-(1<<k),1<<k),0), cntr=max(min(R1[i]-(1<<k),1<<k),0);
				Add00[i+(1<<k)-1].push_back((segment){i-cntl,i,-1});
				Add01[i+(1<<k)-1].push_back((segment){1,i-cntl-1,-sufval[i-cntl]});
				Add00[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,1});
				Add01[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,sufval[i-cntl]});
				Add10[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,-preval[i+(1<<k)-1+cntr]});
				Add11[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,-sufval[i-cntl]*preval[i+(1<<k)-1+cntr]});
			}
			else
			{
				int cntl=max(min(L0[i+(1<<k)-1]-(1<<k),1<<k),0), cntr=max(min(R1[i]-(1<<k),1<<k),0);
				Add00[i+(1<<k)-1].push_back((segment){i-cntl,i,-1});
				Add01[i+(1<<k)-1].push_back((segment){1,i-cntl-1,-sufval[i-cntl]});
				Add00[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,1});
				Add01[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,sufval[i-cntl]});
				Add10[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,-preval[i+(1<<k)-1+cntr]});
				Add11[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,-sufval[i-cntl]*preval[i+(1<<k)-1+cntr]});

				cntl=max(min(L1[i+(1<<k)-1]-(1<<k),1<<k),0), cntr=max(min(R0[i]-(1<<k),1<<k),0);
				Add00[i+(1<<k)-1].push_back((segment){i-cntl,i,-1});
				Add01[i+(1<<k)-1].push_back((segment){1,i-cntl-1,-sufval[i-cntl]});
				Add00[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,1});
				Add01[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,sufval[i-cntl]});
				Add10[i+(1<<k)-1+cntr].push_back((segment){i-cntl,i,-preval[i+(1<<k)-1+cntr]});
				Add11[i+(1<<k)-1+cntr].push_back((segment){1,i-cntl-1,-sufval[i-cntl]*preval[i+(1<<k)-1+cntr]});				
			}
		}

	for(int i=1;i<=m;i++)
		que[R[i]].push_back(make_pair(L[i],i));

	for(int i=0;i<=n;i++)
	{
		for(auto x:Add00[i])
			update2(c00,x.l,x.val), update2(c00,x.r+1,-x.val);

		for(auto x:Add01[i])
			update2(c01,x.l,x.val), update2(c01,x.r+1,-x.val);

		for(auto x:Add10[i])
			update2(c10,x.l,x.val), update2(c10,x.r+1,-x.val);

		for(auto x:Add11[i])
			update2(c11,x.l,x.val), update2(c11,x.r+1,-x.val);

		for(auto x:que[i])
		{
			(ans[x.second] += query2(c00,x.first)*sufval[x.first]%Mod*preval[i]) %= Mod;
			(ans[x.second] += query2(c01,x.first)*preval[i]) %= Mod;
			(ans[x.second] += query2(c10,x.first)*sufval[x.first]) %= Mod;
			(ans[x.second] += query2(c11,x.first)) %= Mod;
		}
	}

	for(int i=1;i<=m;i++)
	{
		int l=L[i], r=R[i];
		long long tot=(val[19][r]-val[19][l-1])*4%Mod;
		for(int k=0;(1<<k)<=r-l+1;k++)
			(tot -= 2*(val[k][r-(1<<k)+1]-val[k][l-1])) %= Mod;
		(tot += ans[i]) %= Mod;
		(tot *= p2[sum[n]]) %= Mod;
		tot += r-l+1;
		(tot *= p2[sum[r]-sum[l-1]]) %= Mod;
		printf("%lld\n",(tot+Mod)%Mod);
	}
	return 0;
}