题目描述

下标从 $0$ 开始的 $\texttt{01}$ 无穷序列 $P$ 由如下方式生成：

• $P_0=\texttt{0}$；
• $P_{2n}=P_{n}$；
• $P_{2n+1}=\texttt{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,1,?}$ 的有限字符串 $S$ 中，将 $S$ 中 $\texttt{?}$ 各自替换成 $\texttt{0}$ 或 $\texttt{1}$，则 $h(S)$ 表示所有可能生成的 $\texttt{01}$ 串 $T$ 的 $g(T)$ 之和。

给定长度为 $n$ 的仅包含 $\texttt{0,1,?}$ 的字符串 $S$，有 $m$ 次询问，每次询问给出 $l,r$，求出 $h(S_lS_{l+1}\cdots S_r)$ 的值。

由于答案可能很大，所以输出答案对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $n,m$。

第二行一个长度为 $n$ 的仅包含 $\texttt{0,1,?}$ 的字符串 $S$。

接下来 $m$ 行，每行两个非负整数 $l,r$，表示一组询问。

输出格式

输出 $m$ 行，对于每组询问输出一行一个整数表示答案。

4 4
??00
0 0
0 1
0 2
0 3

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_1\le r_1 < n$，$0\le l_2\le r_2 < n$。

子任务	$n\le$	$m\le$	特殊性质	分值
1	$15$		A	10
2	$20$	$2\times 10^5$	无
3	$5\times 10^4$		A	5
4		$1$	BC
5			C	15
6	$500$	$10^3$	B	5
7	$10^3$	$2\times 10^3$	BC
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$。