「JEOI-R1」子序列

给定一个仅包含 `0`、`1` 和 `?` 的字符串，你需要将字符串中的每个 `?` 分别替换成 `0` 或 `1` 之一。也就是说替换成一个 $01$ 字符串。求有多少种替换方案，使得替换后的字符串满足：恰好拥有奇数个**不同的**子序列（包含空串）的非空子串的个数为奇数。特别地，如果字符串中不包含 `?`，应将其自身视为唯一的替换方案。 每个数据点会给定一个字符串 $s$ ，然后每次对 $s$ 的一个子串进行询问，答案对 $998244353$ 取模。 ## Input 第一行一个整数 $n$。 第二行一个长为 $n$ 的字符串 $s$，仅包含 `0`、`1` 和 `?`。 第三行一个整数 $m$ 表示询问次数。 接下来 $m$ 行，每行两个整数 $l,r$ 表示对子串 $s_{l,r}$ 进行一次询问。 ## Output 输出 $m$ 行，每行一个整数表示答案，对 $998244353$ 取模。 不存在合法方案则输出 `0`。 [samples] ## Background | 出题 | 标程 | 数据 | 验题 | 题解 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [cq_zry](https://www.luogu.com.cn/user/734533) & [lOlAKME](/user/768786) | [Pekemetier](/user/146070) | ## Note **【样例解释】** 对于【样例\#1】的第一个询问 `1 5`，有 $2$ 种替换方案，分别为字符串 `10001` 和 `10011`。 其中 `10001` 有 $3$ 个子串满足不同的子序列的个数为奇数：`10001`，拥有 $15$ 个不同的子序列；$s'_ {2,3}$ 和 $s'_ {3,4}$ 均为 `00`，都拥有 $3$ 个不同的子序列。 而 `10011` 则拥有 $4$ 个子串满足不同的子序列的个数为奇数，分别为 `1001`、`00`、`0011`、`11`。 `10001` 有奇数个子串满足子序列个数为奇数，因此计入答案；而 `10011` 有偶数个，因此不计入答案。 对于【样例#2】的第一个询问 `1 20`，$s_{1,20}$ 有 $4$ 个 `?`，因此有 $2^4=16$ 种替换方案。 --- **【数据范围】** **本题采用捆绑测试**。 | $\text{Subtask}$ | $n\leq$ | $m\leq$ | 特殊性质 | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10$ | | $10$ | | $2$ | $100$ | $100$ | $s$ 不包含 `?` | $10$ | | $3$ | $500$ | $500$ | $s$ 不包含 `?` | $20$ | | $4$ | $1000$ | $1000$ | | $20$ | | $5$ | $5000$ | $5000$ | | $10$ | | $6$ | $5000$ | $10^5$ | | $10$ | | $7$ | $5\times10^4$ | $3\times 10^5$ | | $20$ | 对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times10^4$，$1\leq m\leq 3\times10^5$，$s$ 仅包含 `0`、`1` 和 `?`。 --- **【提示与说明】** 子串：在原来的字符串中选出一段连续字符组成的字符串。一个长为 $n$ 的字符串有 $\frac{n(n+1)}{2}$ 个子串。例如字符串 `121` 共有 $6$ 个子串，分别为 `1`、`2`、`1`、`12`、`21`、`121`。注意在本题中，空串不算一个子串。 子序列：在原来的字符串中任意删去若干个字符（也可以不删）形成的的字符串。例如字符串 `0110` 拥有 $11$ 个不同的子序列，分别为空串、`0`、`1`、`00`、`01`、`10`、`11`、`010`、`011`、`110`、`0110`。注意在本题中，空串也算一个子序列。