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