#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair

#define FastI
#define FastO
//#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
	int x,y,z;
	tup(int X=0,int Y=0,int Z=0)
	{x=X,y=Y,z=Z;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];
			int top=0;
			do st[top++]=x%10+'0',x/=10;while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' '&&st!='\r')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		char ch=getchar();s=0;
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-'&&(ch=getchar()));
		while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=tf?-s:s;
	}
	inline void edl(){putchar('\n');}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
	#ifdef FastO
	struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
	#endif
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
	inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	const int N=50010; 
	template<class Info,class Tag> struct Segment
	{
	    #define ls(p) (t[p].l+t[p].r)
	    #define rs(p) (ls(p)^1)
	    private:
	        vector<Info> tmp;
	        struct{int l,r;Info v;Tag tg;}t[N<<1];
	        inline void down(int p,Tag tg){t[p].v=t[p].v*tg,t[p].tg=t[p].tg*tg;}
	        inline void spread(int p){down(ls(p),t[p].tg),down(rs(p),t[p].tg),t[p].tg=Tag();}
	        void build(int p,int l,int r)
	        {
	            t[p].l=l,t[p].r=r;
	            if(l==r)return t[p].v=tmp[l-1],void();
	            int mid=l+((r-l)>>1);
	            build(ls(p),l,mid),build(rs(p),mid+1,r);
	            t[p].v=t[ls(p)].v+t[rs(p)].v;
	        }
	        void change(int p,int x,Info v)
	        {
	            if(t[p].l==t[p].r)return t[p].v=v,void();
	            spread(p);
	            change(ls(p)^(x>t[ls(p)].r),x,v);
	            t[p].v=t[ls(p)].v+t[rs(p)].v;
	        }
	        Info ask(int p,int l,int r)
	        {
	            if(l<=t[p].l&&r>=t[p].r)return t[p].v;
	            spread(p);
	            if(r<=t[ls(p)].r)return ask(ls(p),l,r);
	            if(l>t[ls(p)].r)return ask(rs(p),l,r);
	            return ask(ls(p),l,r)+ask(rs(p),l,r);
	        }
	        void modify(int p,int l,int r,Tag tg)
	        {
	            if(l<=t[p].l&&r>=t[p].r)return down(p,tg);
	            spread(p);
	            if(l<=t[ls(p)].r)modify(ls(p),l,r,tg);
	            if(r>t[ls(p)].r)modify(rs(p),l,r,tg);
	            t[p].v=t[ls(p)].v+t[rs(p)].v;
	        }
	        template<class Compare> pair<int,Info>
	        findnex(int p,int x,Info y,Compare cmp)
	        {
	            if(x>t[p].r||!cmp(y,t[p].v))return mp(0,(Info){});
	            if(t[p].l==t[p].r)return mp(t[p].l,t[p].v);
	            spread(p);
	            pair<int,Info> v=findnex(ls(p),x,y,cmp);
	            if(v.fi)return v;
	            return findnex(rs(p),x,y,cmp);
	        }
	        template<class Compare> pair<int,Info>
	        findpre(int p,int x,Info y,Compare cmp)
	        {
	            if(x<t[p].l||!cmp(y,t[p].v))return mp(0,(Info){});
	            if(t[p].l==t[p].r)return mp(t[p].l,t[p].v);
	            spread(p);
	            pair<int,Info> v=findpre(rs(p),x,y,cmp);
	            if(v.fi)return v;
	            return findpre(ls(p),x,y,cmp);
	        }
	    public:
	        void print(int p=1)
	        {
	            if(t[p].l==t[p].r)return t[p].v.print();
	            spread(p),print(ls(p)),print(rs(p));
	        }
	        void printall(int p=1)
	        {
	            write('[',t[p].l,',',t[p].r,']',':');
	            t[p].v.print();
	            spread(p),print(ls(p)),print(rs(p));
	        }
	        void modify(int l,int r,Tag tg){modify(1,l,r,tg);}
	        template<class Compare> pair<int,Info>
	        findnex(int x,Info y,Compare cmp)
	        {return findnex(1,x,y,cmp);}
	        template<class Compare> pair<int,Info>
	        findpre(int x,Info y,Compare cmp)
	        {return findpre(1,x,y,cmp);}
	        void change(int x,Info v){change(1,x,v);}
	        Info ask(int l,int r){return ask(1,l,r);}
	        void init(vector<Info> ve){tmp=ve,build(1,1,ve.size());}
	    #undef ls
	    #undef rs
	};
	struct Tag
	{
		int f[3][3];
	    Tag(int v=0,int vv=0){f[0][0]=f[1][1]=f[2][2]=1,f[0][1]=v,f[1][2]=vv;}
	    Tag operator *(const Tag nd)const
	    {
	        Tag v;memset(v.f,0,sizeof(v.f));
	        for(int i=0;i<3;++i)for(int j=0;j<3;++j)for(int k=i;k<=j;++k)
	        Madd(v.f[i][j],Cmul(f[i][k],nd.f[k][j]));
	        return v;
	    }
	};
	struct Node
	{
		int f[3];
	    Node(int x=0){f[0]=x,f[1]=f[2]=0;}
	    Node operator +(const Node nd)const
	    {
	    	Node v;
	    	for(int i=0;i<3;++i)v.f[i]=Cadd(f[i],nd.f[i]);
	        return v;
	    }
	    Node operator *(const Tag nd)const
	    {
	        Node v;
	        for(int i=0;i<3;++i)for(int j=i;j<3;++j)
	        Madd(v.f[j],Cmul(f[i],nd.f[i][j]));
	        return v;
	    }
	    void print()
	    {
	    	cerr<<"("<<f[0]<<","<<f[1]<<","<<f[2]<<")";
	    }
	};
	int n,m;
	char s[50010];
	int pre[50010];
	int F[16][50010][2],G[16][50010][2];
	vt ve[50010];
	vp qu[50010];
	int pw[50010],ipw[50010];
	int ans[200010];
	void modify(int l1,int r1,int l2,int r2,int v)
	{
		if(l1>r1||l2>r2)return;
		cerr<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<v<<endl;
		ve[l2].eb(tup(l1,r1,v));
		ve[r2+1].eb(tup(l1,r1,MOD-v));
	}
	void mian()
	{
		pw[0]=ipw[0]=1;
		for(int i=1;i<=50000;++i)
		{
			pw[i]=Cmul(pw[i-1],2);
			ipw[i]=Cmul(ipw[i-1],inv2);
		}
		
		read(n,m);
		read(s);
		for(int i=1;i<=n;++i)pre[i]=pre[i-1]+(s[i]=='?');
		for(int i=1;i<=n;++i)
		{
			G[0][i][0]=i+(s[i]=='1'),G[0][i][1]=i+(s[i]=='0');
			F[0][i][0]=i-(s[i]=='1'),F[0][i][1]=i-(s[i]=='0');
		}
		for(int i=0;i<16;++i)
		{
			G[i][0][0]=G[i][0][1]=1;
			F[i][n+1][0]=F[i][n+1][1]=n;
		}
		for(int i=1;i<16;++i)
		{
			for(int j=1;j<=n;++j)
			{
				int r=j+(1<<(i-1)),l=j-(1<<(i-1));
				for(int x=0;x<2;++x)
				{
					F[i][j][x]=(F[i-1][j][x]==r-1?F[i-1][r][x^1]:F[i-1][j][x]);
					G[i][j][x]=(G[i-1][j][x]==l+1?G[i-1][l][x^1]:G[i-1][j][x]);
				}
			}
		}
		for(int i=1;i<n;++i)
		{
			for(int x=0;x<2;++x)for(int y=0;y<2;++y)
			modify(G[15][i][x],i,i+1,F[15][i+1][y],1);
		}
		for(int i=0;i<16;++i)
		{
			for(int j=2;j+(1<<i)<=n;++j)
			{
				int l=j-1,r=j+(1<<i);
				for(int x=0;x<2;++x)
				{
					if(F[i][j][x]==j+(1<<i)-1)
					modify(G[i][l][x^1^(i&1)],l,r,F[i][r][x^1],MOD-1);
				}
			}
		}
		
		int x,y;
		for(int i=1;i<=m;++i)
		{
			read(x,y); 
			++x,++y;
			qu[y].eb(mp(x,i));
			int tmp=pre[y]-pre[x-1];
			Madd(ans[i],Cmul(y-x+1,pw[tmp]));
		}
		
		Segment<Node,Tag> sgt;
		vector<Node> VE;
		sgt.init(vector<Node>(n));
		
		for(int i=1;i<=n;++i)
		{
			sgt.change(i,Node(pw[pre[i-1]]));
			for(auto [x,y,z]:ve[i])
			sgt.modify(x,y,Tag(z));
			sgt.modify(1,n,Tag(0,ipw[pre[i]]));
			for(auto [x,y]:qu[i])
			Madd(ans[y],Cmul(pw[pre[i]],sgt.ask(x,n).f[2],ipw[pre[x-1]]));
//			sgt.print();
//			cerr<<endl;
//			for(int j=1;j<=n;++j)cerr<<"("<<g[j][0]<<","<<g[j][1]<<","<<g[j][2]<<")";
//			cerr<<endl;
		}
		for(int i=1;i<=m;++i)write(ans[i],'\n');
	}
	inline void Mian()
	{
		int T=1;
//		read(T);
		while(T--)mian();
	}
}
bool ED;
signed main()
{
//	ios::sync_with_stdio(0);
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	double st=clock();
	WrongAnswer_90::Mian();
	double ed=clock();
 	cerr<<endl;
 	cerr<<"Time: "<<ed-st<<" ms\n";
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}