#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
#define int long long
using pii=pair<int,int>;
#define endl "\n"
#define pb push_back
const int N = 2e6+10;
struct node{
    int l,r,s0,s1,cn1;
    int fl;
}tr[N];

#define mid (l+r>>1)
#define u tr[i]
int cnt;
void now(int &i){
    i = ++cnt;
    u.l = u.r = u.cn1 = u.s0 = u.s1 = 0;
    u.fl = 0;
}
string s1;

void up(int i){
    node &l = tr[u.l],&r = tr[u.r];
    u.cn1 = l.cn1+r.cn1;
    u.s0  = l.s0+r.s0;
    u.s1 = l.s1+r.s1;
}

void update(int i,int l,int r){
    int cn = r-l+1;
    u.cn1 = cn-u.cn1;
    swap(u.s0,u.s1);
    u.fl ^= 1;
}

void down(int i,int l,int r){
    if(!u.fl)return;
    update(u.l,l,mid);
    update(u.r,mid+1,r);
    u.fl = 0;
    return;
}

void build(int &i,int l,int r){
    now(i);
    if(l == r){
        int fl = s1[l-1] == '1';
        if(fl == 1)u.cn1++,u.s1 += l;
        else u.s0 += l;
        return;
    }
    build(u.l,l,mid);
    build(u.r,mid+1,r);
    up(i);
}

void re(int i,int l,int r,int L,int R){
    if(l > R||r < L)return;
    if(!i)return;
    if(l >= L&&r <= R){
        update(i,l,r);
        return;
    }
    down(i,l,r);
    re(u.l,l,mid,L,R);
    re(u.r,mid+1,r,L,R);
    up(i);
}

int qu(int i,int l,int r,int L,int R,int fl){
    if(l > R||r < L)return 0;
    if(!i)return 0;
    if(l >= L&&r <= R){
        if(fl == 1)return u.s1;
        else return u.s0;
    }
    down(i,l,r);
    int res = qu(u.l,l,mid,L,R,fl)+qu(u.r,mid+1,r,L,R,fl);
    up(i);
    return res;
}

const int mod = 998244353;
void solve(int n)
{
    int q,root = 0;
    cnt = 0;
    cin>>q>>s1;
    build(root,1,n);
    int s1 = qu(root,1,n,1,3,0);
    //cout<<" s1 = "<<s1<<endl;
    while(q--){
        int l,r;
        cin>>l>>r;
        re(root,1,n,l,r);
        int k = tr[root].cn1;
        int s1 = qu(root,1,n,k+1,n,1);
        int s0 = qu(root,1,n,1,k-1,0);
        //cout<<"k = "<<k<<" s1 = "<<s1<<" s0 = "<<s0<<endl;
        if(qu(root,1,n,k,k,1) == k){
            cout<<(s1-s0+k)%mod<<endl;
        }
        else {
            cout<<(s1-s0)%mod<<endl;
        }
    }
}

signed main()
{
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    #endif
    int _=1;
    while(cin>>_) solve(_);
    return 0;
}