Odd Subsequence Substrings Replacement

You are given a string s consisting of only the characters 0, 1 and ?. For every occurrence of ? you must replace it with either 0 or 1 (each independently). Such a replacement is called a replacement scheme. When s does not contain any ?, consider it as a unique replacement scheme.

After replacing, consider the obtained string t. For each non-empty substring u of t, let \( D(u) \) be the number of distinct subsequences of u, including the empty subsequence (hence, the empty string is always counted). We say that u has the odd subsequence property if \( D(u) \) is odd. For example, for u = "0", the distinct subsequences are \( \{ "", "0" \} \) (a total of 2, which is even); for u = "00", the distinct subsequences are \( \{ "", "0", "00" \} \) (3, which is odd).

Your task is: Given a query substring of s (specified by two indices, 1-indexed), count the number of replacement schemes for that substring such that the total number of its non-empty substrings having the odd subsequence property is odd. Since the answer could be very large, output it modulo \(998244353\).

Note: A substring is a contiguous segment of the string. A subsequence is obtained by deleting zero or more characters (not necessarily contiguous) from the string. In the computation of \( D(u) \), the empty subsequence is included.

inputFormat

The first line contains a string s consisting only of characters 0, 1, and ?.

The second line contains an integer q representing the number of queries.

Each of the next q lines contains two integers l and r (1-indexed), representing the substring s[l...r] for which you should answer the query.

outputFormat

For each query, output a single integer — the number of replacement schemes for the queried substring that yield an odd number of non-empty substrings having an odd number of distinct subsequences, modulo \(998244353\).

sample

0?1
1
1 3

2