The infinite $\texttt{01}$ sequence $P$ with $0$-based indexing is generated as follows:

• $P_0=0$;
• $P_{2n}=P_{n}$;
• $P_{2n+1}=1-P_{n}$.

The first few terms of the sequence $P$ are given below:

$$ \texttt{01101001100101101001011001101001}\cdots $$

For convenience, we treat $P$ as a string, where the string indices are $0$-based.

Define $f(S)$ as $1$ if the finite $\texttt{01}$ string $S$ is a substring of $P$, and $0$ otherwise.

Define $g(S)$ as the number of substrings of a finite $\texttt{01}$ string $S$ that are also substrings of $P$, i.e.:

$$ g(S)=\sum_{0\le l \le r < |S|}f(S_lS_{l+1}\cdots S_r) $$

Next, we define $h(S)$: for a finite string $S$ containing only $\texttt{0}, \texttt{1}, \texttt{?}$, $h(S)$ is the sum of $g(T)$ over all possible $\texttt{01}$ strings $T$ obtained by replacing each $\texttt{?}$ in $S$ with either $\texttt{0}$ or $\texttt{1}$.

Given a string $S$ of length $n$ containing only $\texttt{0}, \texttt{1}, \texttt{?}$, there are $m$ queries. Each query provides $l$ and $r$, and you are asked to calculate the value of $h(S_lS_{l+1}\cdots S_r)$.

Since the answer can be very large, output the result modulo $998244353$.

Input

The first line contains two positive integers $n, m$.

The second line contains a string $S$ of length $n$ consisting only of $\texttt{0}, \texttt{1}, \texttt{?}$.

The next $m$ lines each contain two non-negative integers $l, r$, representing a query.

Output

Output $m$ lines, each containing a single integer representing the answer to the corresponding query.

Examples

Input 1

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

Output 1

2
12
23
35

Input 2

(input data)

Output 2

(output data)

Note

Examples 2 satisfy $n, m \le 15$ and special property C.

Input 3

(input data)

Output 3

(output data)

Note

Examples 3 satisfy $n, m \le 100$ and special property B.

Input 4

(input data)

Output 4

(output data)

Note

Examples 4 satisfy $n, m \le 10^3$ and special property BC.

Input 5

(input data)

Output 5

(output data)

Note

Examples 5 satisfy $n, m \le 10^3$ and special property A.

Constraints

For $100\%$ of the data, $1 \le n \le 5 \times 10^4$, $1 \le m \le 2 \times 10^5$, $0 \le l \le r < n$.

• Special Property A: $r-l+1 \le 15$;
• Special Property B: The number of $\texttt{?}$ in $S$ does not exceed 8;
• Special Property C: $l=0$.