题目描述

下标从 $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$。

• 特殊性质 A：$r-l+1 \le 15$；
• 特殊性质 B：$S$ 中 $\texttt{?}$ 的个数不超过 8；
• 特殊性质 C：$l=0$。