题目描述
下标从 $0$ 开始的 $\texttt{01}$ 无穷序列 $P$ 由如下方式生成：
- $P_0=0$；
- $P_{2n}=P_{n}$；
- $P_{2n+1}=1-P_{n}$。
这里给出 $P$ 序列的前若干项：
$$ \texttt{01101001100101101001011001101001}\cdots $$
方便起见，接下来将 $P$ 看做一个字符串，且字符串的下标均从 $0$ 开始。
定义 $f(S)$ 表示有限 $\texttt{01}$ 串 $S$ 是否为 $P$ 的子串，若是，则 $f(S)=1$，否则为 $0$。
定义 $g(S)$ 表示有限 $\texttt{01}$ 串 $S$ 中【是 $P$ 的子串】的子串个数，即：
$$ g(S)=\sum_{0\le l \le r < |S|}f(S_lS_{l+1}\cdots S_r) $$
接下来定义 $h(S)$：对于一个仅包含 $\texttt{0},\texttt{1},\texttt{?}$ 的有限字符串 $S$，将 $S$ 中 $\texttt{?}$ 各自替换成 $\texttt{0}$ 或 $\texttt{1}$，则 $h(S)$ 表示所有可能生成的 $\texttt{01}$ 串 $T$ 的 $g(T)$ 之和。
给定长度为 $n$ 的仅包含 $\texttt{0},\texttt{1},\texttt{?}$ 的字符串 $S$，有 $m$ 次询问，每次询问给出 $l,r$，求出 $h(S_lS_{l+1}\cdots S_r)$ 的值。
由于答案可能很大，所以输出答案对 $998244353$ 取模的结果。
输入格式
第一行两个正整数 $n,m$。
第二行一个长度为 $n$ 的仅包含 $\texttt{0},\texttt{1},\texttt{?}$ 的字符串 $S$。
接下来 $m$ 行，每行两个非负整数 $l,r$，表示一组询问。
输出格式
输出 $m$ 行，对于每组询问输出一行一个整数表示答案。
样例
样例输入 1
4 4 ??00 0 0 0 1 0 2 0 3
样例输出 1
2 12 23 35
样例 2
见下发文件，满足 $n,m \le 15$ 和特殊性质 C。
样例 3
见下发文件，满足 $n,m \le 100$ 和特殊性质 B。
样例 4
见下发文件，满足 $n,m \le 10^3$ 和特殊性质 BC。
样例 5
见下发文件，满足 $n,m \le 10^3$ 和特殊性质 A。
数据范围
对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^4$，$1 \le m \le 2 \times 10^5$，$0 \le l \le r < n$。
| 子任务 | $n \le$ | $m \le$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| 1 | 15 | 15 | A | 10 |
| 2 | 20 | $2 \times 10^5$ | 无 | 10 |
| 3 | $5 \times 10^4$ | A | 5 | |
| 4 | 1 | BC | 5 | |
| 5 | C | 15 | ||
| 6 | 500 | $10^3$ | B | 5 |
| 7 | $10^3$ | $2 \times 10^3$ | BC | 5 |
| 8 | $5 \times 10^3$ | $10^5$ | C | 10 |
| 9 | $2 \times 10^4$ | 无 | 15 | |
| 10 | $5 \times 10^4$ | $2 \times 10^5$ | 无 | 20 |
- 特殊性质 A：$r-l+1 \le 15$；
- 特殊性质 B：$S$ 中 $\texttt{?}$ 的个数不超过 8；
- 特殊性质 C：$l=0$。