Background

Problem Description

You are given a string that contains only 0, 1, and ?. You need to replace each ? with either 0 or 1. That is, turn it into a $01$ string. Count how many replacement schemes make the resulting string satisfy the following condition:

Among all non-empty substrings, the number of substrings that have an odd number of distinct subsequences (including the empty string) is odd.

In particular, if the string does not contain ?, then the string itself should be treated as the only replacement scheme.

Each test gives a string $s$, and then asks queries on substrings of $s$. Output each answer modulo $998244353$.

Input Format

The first line contains an integer $n$.

The second line contains a string $s$ of length $n$, consisting only of 0, 1, and ?.

The third line contains an integer $m$, the number of queries.

The next $m$ lines each contain two integers $l, r$, meaning a query on the substring $s_{l,r}$.

Output Format

Output $m$ lines, each containing one integer: the answer modulo $998244353$.

If there is no valid scheme, output 0.

5
100?1
5
1 5
1 4
2 5
3 4
1 3

1
0
1
1
1

20
1110??01001010?1?110
20
1 20
5 16
11 16
10 13
5 14
13 17
1 18
1 7
6 9
15 19
12 17
17 18
4 11
3 13
13 15
18 19
2 8
7 13
4 15
9 18

3
2
2
0
4
2
13
3
0
1
3
1
2
2
2
1
2
1
1
3

Hint

Sample Explanation

For the first query 1 5 in Sample #1, there are $2$ replacement schemes: the strings 10001 and 10011.

For 10001, there are $3$ substrings whose number of distinct subsequences is odd: 10001, which has $15$ distinct subsequences; and $s'_{2,3}$ and $s'_{3,4}, both equal to 00`, each having $3$ distinct subsequences.

For 10011, there are $4$ substrings whose number of distinct subsequences is odd: 1001, 00, 0011, and 11.

10001 has an odd number of such substrings, so it is counted in the answer; 10011 has an even number, so it is not counted.

For the first query 1 20 in Sample #2, $s_{1,20}$ has $4$ ?, so there are $2^4 = 16$ replacement schemes.

Constraints

This problem uses bundled subtasks.

For $100\%$ of the testdata, $1\leq n\leq 5\times10^4$, $1\leq m\leq 3\times10^5$, and $s$ contains only 0, 1, and ?.

Notes and Explanation

Substring: a string formed by choosing a continuous segment from the original string. A string of length $n$ has $\frac{n(n+1)}{2}$ substrings. For example, the string 121 has $6$ substrings: 1, 2, 1, 12, 21, 121. Note that in this problem, the empty string is not a substring.

Subsequence: a string formed by deleting any number of characters from the original string (possibly deleting none). For example, the string 0110 has $11$ distinct subsequences: the empty string, 0, 1, 00, 01, 10, 11, 010, 011, 110, 0110. Note that in this problem, the empty string is also considered a subsequence.

Translated by ChatGPT 5