#ifdef LOCAL
#include "S:/Codes/VSCode/algo/Lib/tools/debug.h"
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int P = 998244353;

IL void qm (int &x) {
  x += x >> 31 & P;
}

IL constexpr int qpow (int b, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, b = (LL)b * b % P) if (k & 1) r = (LL)r * b % P;
  return r;
}

constexpr int N = 5e4 + 9;
int n, m, pre[N];
char s[N];

struct whq {
  int l, i;
  whq (int a, int b) : l(a), i(b) {}
};
vector<whq> q[N];

int ns[N << 2];

struct zlt {
  int l, r, x;
  zlt (int a, int b, int c) : l(a), r(b), x(c) {}
};
vector<zlt> md[N];

bool fp[18][N], gp[18][N];
bool fq[18][N], gq[18][N];

#define ls p << 1
#define rs p << 1 | 1
#define m ((l + r) >> 1)

struct SGT {
  struct C {
    int s, h, coef, ad, adh, lz;
  } t[N << 2];

  void up (int p) {
    qm(t[p].s = t[ls].s + t[rs].s - P);
    qm(t[p].h = t[ls].h + t[rs].h - P);
  }

  void phis (int p, int x) {
    t[p].h = (t[p].h + t[p].s * (LL)x) % P;
    t[p].adh = (t[p].adh + t[p].ad * (LL)x) % P;
    qm(t[p].lz += x - P);
  }

  void pad (int p, int x) {
    t[p].s = (t[p].s + t[p].coef * (LL)x) % P;
    qm(t[p].ad += x - P);
  }

  void padh (int p, int x) {
    t[p].h = (t[p].h + t[p].coef * (LL)x) % P;
    qm(t[p].adh += x - P);
  }

  void down (int p) {
    if (int &x = t[p].lz) {
      phis(ls, x);
      phis(rs, x);
      x = 0;
    }
    if (int &x = t[p].ad) {
      pad(ls, x);
      pad(rs, x);
      x = 0;
    }
    if (int &x = t[p].adh) {
      padh(ls, x);
      padh(rs, x);
      x = 0;
    }
  }

  void bld (int l, int r, int p) {
    if (l == r) {
      t[p].coef = qpow(2, pre[l - 1]);
      return;
    }
    bld(l, m, ls);
    bld(m + 1, r, rs);
    qm(t[p].coef = t[ls].coef + t[rs].coef - P);
  }

  void mdy (int ql, int qr, int l, int r, int p, int x) {
    if (ql <= l && r <= qr) {
      pad(p, x);
      return;
    }
    down(p);
    if (ql <= m) {
      mdy(ql, qr, l, m, ls, x);
    }
    if (m < qr) {
      mdy(ql, qr, m + 1, r, rs, x);
    }
    up(p);
  }

  int qry (int ql, int qr, int l, int r, int p) {
    if (ql <= l && r <= qr) {
      return t[p].h;
    }
    down(p);
    int s = 0;
    if (ql <= m) {
      s = qry(ql, qr, l, m, ls);
    }
    if (m < qr) {
      qm(s += qry(ql, qr, m + 1, r, rs) - P);
    }
    return s;
  }
} S;

#undef m

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> (s + 1);
  L (i, 1, n) {
    pre[i] = pre[i - 1] + (s[i] == '?');
  }
  L (i, 1, m) {
    int l, r;
    cin >> l >> r;
    ++l, ++r;
    q[r].eb(l, i);
    ns[i] = (r - l + 1) * (LL)qpow(2, pre[r] - pre[l - 1]) % P;
  }
  L (i, 1, n) {
    fp[0][i] = fq[0][i] = s[i] != '1';
    gp[0][i] = gq[0][i] = s[i] != '0';
  }
  L (i, 1, 17) {
    L (j, 1, n - (1 << i) + 1) {
      fp[i][j] = fp[i - 1][j] & gp[i - 1][j + (1 << (i - 1))];
      gp[i][j] = gp[i - 1][j] & fp[i - 1][j + (1 << (i - 1))];
    }
    L (j, 1 << i, n) {
      fq[i][j] = fq[i - 1][j] & gq[i - 1][j - (1 << (i - 1))];
      gq[i][j] = gq[i - 1][j] & fq[i - 1][j - (1 << (i - 1))];
    }
  }
  auto getl = [&] (int i) {
    vi a;
    L (s, 0, 1) {
      int p = i + 1, o = s;
      R (l, 17, 0) {
        if ((o ? fq : gq)[l][p - 1]) {
          p -= 1 << l;
          o ^= 1;
        }
      }
      a.eb(p);
    }
    return a;
  };
  auto getr = [&] (int i) {
    vi b;
    L (s, 0, 1) {
      int p = i - 1, o = s;
      R (l, 17, 0) {
        if ((o ? fp : gp)[l][p + 1]) {
          p += 1 << l;
          o ^= 1;
        }
      }
      b.eb(p);
    }
    return b;
  };
  L (i, 1, n - 1) {
    vi a = getl(i), b = getr(i + 1);
    for (int x : a) if (x <= i) {
      for (int y : b) if (y > i) {
        md[i + 1].eb(x, i, 1);
        md[y + 1].eb(x, i, P - 1);
      }
    }
  }
  for (int k = 0; (1 << k) <= n - 2; ++k) {
    L (i, 2, n - (1 << k)) {
      int l = i, r = i + (1 << k) - 1;
      vi a = getl(r);
      vi b = getr(l);
      if (k & 1) {
        swap(b[0], b[1]);
      }
      L (i, 0, 1) {
        int x = a[i], y = b[i];
        x = max(x, l - (1 << k));
        y = min(y, r + (1 << k));
        if (x < l && y > r) {
          md[r + 1].eb(x, l - 1, P - 1);
          md[y + 1].eb(x, l - 1, 1);
        }
      }
    }
  }
  S.bld(1, n, 1);
  L (i, 1, n) {
    for (auto [l, r, x] : md[i]) {
      S.mdy(l, r, 1, n, 1, x);
    }
    S.phis(1, qpow(2, P - 1 - pre[i]));
    for (auto [l, x] : q[i]) {
      int s = S.qry(l, i, 1, n, 1);
      s = (LL)s * qpow(2, P - 1 - pre[l - 1]) % P * qpow(2, pre[i]) % P;
      qm(ns[x] += s - P);
    }
  }
  L (i, 1, m) {
    cout << ns[i] << '\n';
  }
}
// I love WHQ!

answer.code: In function ‘int main()’:
answer.code:146:17: error: no match for ‘operator>>’ (operand types are ‘std::basic_istream<char>::__istream_type’ {aka ‘std::basic_istream<char>’} and ‘char*’)
  146 |   cin >> n >> m >> (s + 1);
      |   ~~~~~~~~~~~~~ ^~ ~~~~~~~
      |            |          |
      |            |          char*
      |            std::basic_istream<char>::__istream_type {aka std::basic_istream<char>}
In file included from /usr/include/c++/13/sstream:40,
                 from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
                 from answer.code:5:
/usr/include/c++/13/istream:325:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  325 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/13/istream:325:7: note:   conversion of argument 1 would be ill-formed:
answer.code:146:23: error: cannot bind non-const lvalue reference of type ‘void*&’ to an rvalue of type ‘void*’
  146 |   cin >> n >> m >> (s + 1);
      |                    ~~~^~~~
/usr/include/c++/13/istream:201:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  201 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:201:7: note:   conversion of argument 1 would be ill-formed:
answer.code:146:23: error: invalid conversion from ‘char*’ to ‘long long unsigned int’ [-fpermissive]
  146 |   cin >> n >> m >> (s + 1);
      |                    ~~~^~~~
      |                       |
      |                       char*
answer.code:146:23: error: cannot bind rvalue ‘(long long unsigned int)(((char*)(& s)) + 1)’ to ‘long long unsigned int&’
/usr/include/c++/13/istream:197:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  197 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:197:7: note:   conversion of argument 1 would be ill-formed:
answer.code:146:23: error: invalid conversion from ‘char*’ to ‘long long int’ [-fpermissive]
  146 |   cin >> n >> m >> (s + 1);
      |                    ~~~^~~~
      |                       |
      |                       char*
answer.code:146:23: error: cannot bind rvalue ‘(long long int)(((char*)(& s)) + 1)’ to ‘long long int&’
/usr/include/c++/13/istream:192:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  192 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:192:7: note:   conversion of argument 1 would be ill-formed:
answer.code:146:23: error: invalid conversion from ‘char*’ to ‘long unsigned int’ [-fpermissive]
  146 |   cin >> n >> m >> (s + 1);
      |                    ~~~^~~~
      |                       |
      |                       char*
answer.code:146:23: error: cannot bind rvalue ‘(long unsigned int)(((char*)(& s)) + 1)’ to ‘long unsigned int&’
/usr/include/c++/13/istream:188:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:188:7: note:   conversion of argument 1 would be ill-formed:
answer.code:146:23: error: invalid conversion from ‘char*’ to ‘long int’ [-fpermissive]
  146 |   cin >> n >> m >> (s + 1);
      |                    ~~~^~~~
      |                       |
      |                       char*
answer.code:146:23: error: cannot bind rvalue ‘(long int)(((char*)(& s)) + 1)’ to ‘long int&’
/usr/include/c++/13/istream:184:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:184:7: note:   conversion of argument 1 would be ill-formed:
answer.code:146:23: error: invalid conversion from ‘char*’ to ‘unsigned int’ [-fpermissive]
  146 |   cin >> n >> m >> (s + 1...