#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=5e4+10,M=2e5+10,K=__lg(N)+2,mod=998244353;
int n,m,cnt[N],pw[N];
int f[K][N][2],g[K][N][2];
char a[N];
struct ques{
	int l,r;
}q[M];
struct val_t{
	int sum,ans,pw,val;
	val_t()=default;
	val_t(int a,int b,int c,int d):sum(a),ans(b),pw(c),val(d){}
};
val_t operator + (const val_t &a,const val_t &b){
	return val_t(
		(1ll*a.sum*b.pw+b.sum)%mod,(1ll*a.ans*b.pw+b.ans)%mod,
		1ll*a.pw*b.pw%mod,(1ll*a.val*b.pw+b.val)%mod
	);
}
struct laz_t{
	int laz,pw,sum,val;
	laz_t():laz(0),pw(1),sum(0),val(0){};
	laz_t(int a,int b,int c,int d):laz(a),pw(b),sum(c),val(d){}
	operator bool()const{
		return laz||pw!=1||sum||val;
	}
};
val_t& operator += (val_t &a,const laz_t &b){
	a.ans=(1ll*a.ans*b.pw+1ll*a.sum*b.sum+1ll*a.val*b.val)%mod;
	a.sum=(a.sum+1ll*a.val*b.laz)%mod;
	return a;
}
laz_t& operator += (laz_t &a,const laz_t &b){
	a.pw=1ll*a.pw*b.pw%mod;
	a.sum=(1ll*a.sum*b.pw+b.sum)%mod;
	a.val=(1ll*a.val*b.pw+1ll*a.laz*b.sum+b.val)%mod;
	a.laz=(a.laz+b.laz)%mod;
	return a;
}
int lim;
val_t t[N<<2];
laz_t laz[N<<2];
#define pushup(rt) \
	(t[rt].sum=(1ll*t[rt<<1].sum*t[rt<<1|1].pw+t[rt<<1|1].sum)%mod,\
	t[rt].ans=(1ll*t[rt<<1].ans*t[rt<<1|1].pw+t[rt<<1|1].ans)%mod)
#define pushlaz(rt,x) (t[rt]+=x,laz[rt]+=x)
#define pushdown(rt) \
	laz[rt]&&(pushlaz(rt<<1,laz[rt]),\
	pushlaz(rt<<1|1,laz[rt]),\
	laz[rt]=laz_t(),0)
void build(){
	for(lim=1;lim<=n+1;lim<<=1);
	for(int i=1;i<=n;i++)t[lim+i]=val_t(0,0,1+(a[i]=='?'),1);
	for(int i=lim;i>=1;i--)t[i]=t[i<<1]+t[i<<1|1];
}
void push(int l,int r){
	static int stk[99],top;
	for(top=0,l+=lim-1,r+=lim+1;l^r^1;){
		stk[++top]=l>>=1,stk[++top]=r>>=1;
	}
	for(;l>>=1;)stk[++top]=l;
	for(int i=top;i>=1;i--)pushdown(stk[i]);
}
void update(int l,int r,const laz_t &x){
	push(l,r);
	for(l+=lim-1,r+=lim+1;l^r^1;){
		~l&1&&(pushlaz(l^1,x),0);
		r&1&&(pushlaz(r^1,x),0);
		l>>=1,r>>=1,pushup(l),pushup(r);
	}
	for(;l>>=1;)pushup(l);
}
val_t query(int l,int r){
	push(l,r);
	val_t a=val_t(0,0,1,0),b=a;
	for(l+=lim-1,r+=lim+1;l^r^1;l>>=1,r>>=1){
		~l&1&&(a=a+t[l^1],0);
		r&1&&(b=t[r^1]+b,0);
	}
	return a+b;
}
vector<int>o[N];
vector<tuple<int,int,int>>p[N];
int ans[M];
void insert(int l,int r,int x,int y,int w){
	if(l>r||x>y)return;
	p[r].push_back({x,y,w});
	p[l-1].push_back({x,y,-w});
}
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int main(){
	fin>>n>>m;
	for(int i=1;i<=n;i++)fin>>a[i];
	for(int i=n;i>=1;i--)cnt[i]=cnt[i+1]+(a[i]=='?');
	for(int i=pw[0]=1;i<=n;i++)pw[i]=pw[i-1]*2%mod;
	for(int i=1;i<=m;i++){
		fin>>q[i].l>>q[i].r,++q[i].l,++q[i].r;
		o[q[i].l].push_back(i);
	}
	for(int i=1;i<=n;i++)for(int c:{0,1}){
		f[0][i][c]=g[0][i][c]=a[i]!='0'+!c;
	}
	for(int i=0;(1<<i)<=n;i++){
		for(int j=1;j<=n;j++){
			for(int c:{0,1}){
				f[i+1][j][c]=f[i][j][c]==(1<<i)?f[i][j+(1<<i)][!c]+(1<<i):f[i][j][c];
				g[i+1][j][c]=g[i][j][c]==(1<<i)?g[i][j-(1<<i)][!c]+(1<<i):g[i][j][c];
			}
		}
	}
	for(int i=1,k=__lg(n)+1;i<n;i++){
		for(int x:{0,1})for(int y:{0,1}){
			insert(i-g[k][i][x]+1,i,i+1,i+f[k][i+1][y],1);
		}
	}
	for(int k=0;(1<<k)<=n;k++){
		for(int i=1,j=1+(1<<k);j<n;i++,j++){
			for(int x:{0,1})if(f[k][i+1][x]==(1<<k)){
				int y=k&1^x;
				insert(i-g[k][i][!y]+1,i,j+1,j+f[k][j+1][!x],-1);
			}
		}
	}
	for(int i=1;i<=n;i++)insert(i,i,i,i,1+(a[i]=='?'));
	build();
	for(int i=n;i>=1;i--){
		sort(all(p[i]));
		for(int l=0,r;l<p[i].size();l=r){
			auto [st,ed,sum]=p[i][l];
			for(r=l+1;r<p[i].size()&&st==get<0>(p[i][r])&&ed==get<1>(p[i][r]);r++)sum+=get<2>(p[i][r]);
			update(st,ed,laz_t(sum,1,0,0));
		}
		update(1,n,laz_t(0,1+(a[i]=='?'),1,0));
		for(int id:o[i])ans[id]=query(q[id].l,q[id].r).ans;
	}
	for(int i=1;i<=m;i++)(ans[i]+=mod)%=mod;
	for(int i=1;i<=m;i++)fout<<ans[i]<<'\n';
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif