#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define WTHI(v) {unsigned _z=v,_n=0;long _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;}
#define WTLO(v) {unsigned _z=v,_n=8;long _d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;}
#define wt(v) if(v>=100000000){WTLO(v/10);*wp++=v%10+'0';}else{WTHI(v);}
#define rep(v,e) for(typeof(e) v=0;v<e;++v)
#define rreps(v,s,e) for(typeof(e) v=e;--v>=s;)
#define times(e) for(typeof(e) _=e;_--;)
#define chmax(v,a) (v=v>=a?v:a)
#define MD 998244353

typedef unsigned long ulong;

char wbuf[1<<25];

typedef struct{
	unsigned m00,m01,m02;
	unsigned m10,m11,m12;
	int skip;
}N;

N tree[1<<17];

int main(){
	rd_init();
	int n=rd();
	int q=rd();
	rep(i,n){
		N*np=&tree[1<<16|i];
		np->m00=1;
		np->m11=1;
		int c=*rp++;
		if(c=='0'){
			np->m01=1;
		}else{
			np->m10=1;
			np->m12=1;
		}
	}
	rreps(i,1,1<<16){
		N*np=&tree[i];
		N*c0=&tree[i*2+0];
		N*c1=&tree[i*2+1];
		np->m00=((ulong)c1->m00*(ulong)c0->m00+(ulong)c1->m01*(ulong)c0->m10)%MD;
		np->m01=((ulong)c1->m00*(ulong)c0->m01+(ulong)c1->m01*(ulong)c0->m11)%MD;
		np->m02=((ulong)c1->m00*(ulong)c0->m02+(ulong)c1->m01*(ulong)c0->m12+c1->m02)%MD;
		np->m10=((ulong)c1->m10*(ulong)c0->m00+(ulong)c1->m11*(ulong)c0->m10)%MD;
		np->m11=((ulong)c1->m10*(ulong)c0->m01+(ulong)c1->m11*(ulong)c0->m11)%MD;
		np->m12=((ulong)c1->m10*(ulong)c0->m02+(ulong)c1->m11*(ulong)c0->m12+c1->m12)%MD;
	}
	++rp;
	char*wp=wbuf;
	times(q){
		int t=*rp;
		rp+=2;
		int l=1<<16|rd()-1;
		int r=1<<16|rd();
		if(t=='1'){
			while(l<r){
				int x=tree[l].skip;
				if(x){
					chmax(tree[l].skip,r);
					l=x;
				}else{
					tree[l].skip=r;
					{
						N*np=&tree[l];
						np->m00=1; np->m01=0; np->m02=0; 
						np->m10=0; np->m11=1; np->m12=0;
					}
					for(int i=l>>1;i;i>>=1){
						N*np=&tree[i];
						N*c0=&tree[i*2+0];
						N*c1=&tree[i*2+1];
						np->m00=((ulong)c1->m00*(ulong)c0->m00+(ulong)c1->m01*(ulong)c0->m10)%MD;
						np->m01=((ulong)c1->m00*(ulong)c0->m01+(ulong)c1->m01*(ulong)c0->m11)%MD;
						np->m02=((ulong)c1->m00*(ulong)c0->m02+(ulong)c1->m01*(ulong)c0->m12+c1->m02)%MD;
						np->m10=((ulong)c1->m10*(ulong)c0->m00+(ulong)c1->m11*(ulong)c0->m10)%MD;
						np->m11=((ulong)c1->m10*(ulong)c0->m01+(ulong)c1->m11*(ulong)c0->m11)%MD;
						np->m12=((ulong)c1->m10*(ulong)c0->m02+(ulong)c1->m11*(ulong)c0->m12+c1->m12)%MD;
					}
					l+=1;
				}
			}
		}
		if(t=='2'){
			unsigned f=0;
			unsigned v0=0;
			unsigned v1=0;
			while(l<r){
				if(l&1){
					N*np=&tree[l];
					unsigned u0=((ulong)np->m00*v0+(ulong)np->m01*v1+np->m02)%MD;
					unsigned u1=((ulong)np->m10*v0+(ulong)np->m11*v1+np->m12)%MD;
					v0=u0;
					v1=u1;
				}
				l=l+1>>1;
				f=f<<1|r&1;
				r>>=1;
			}
			while(f){
				r=r<<1|f&1;
				f>>=1;
				if(r&1){
					N*np=&tree[r-1];
					unsigned u0=((ulong)np->m00*v0+(ulong)np->m01*v1+np->m02)%MD;
					unsigned u1=((ulong)np->m10*v0+(ulong)np->m11*v1+np->m12)%MD;
					v0=u0;
					v1=u1;
				}
			}
			wt((v0+v1)%MD);
			*wp++='\n';
		}
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}