CF2187D.Cool Problem

There are two integer constants $x$ and $y$.

For a binary$^{\text{∗}}$ string $r$ of length $n$, we define its generating array as an array $c=[c_0,c_1,\ldots,c_n]$ such that $c_0=0$, and for each $1 \le i \le n$:

• If $r_i=\mathtt{0}$, then $c_i=x+c_{i-1}$;
• If $r_i=\mathtt{1}$, then $c_i=y-c_{i-1}$.

Additionally, we define $f(r)=\sum\limits_{i=1}^n c_i$.

You are given an incomplete binary string $s$ of length $n$, where some characters in it are missing, represented by $\mathtt{?}$. An integer $k$ is called cool if and only if there exists a way to replace each $\mathtt{?}$ in $s$ with either $\mathtt{0}$ or $\mathtt{1}$, such that $f(s)=k$.

Your task is to calculate the sum of all cool integers, modulo $998\,244\,353$.

$^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$.

存在两个整数常量 $x$ 和 $y$。

对于一个长度为 $n$ 的二进制$^{\text{∗}}$字符串 $r$，我们定义其生成数组为一个数组 $c=[c_0,c_1,\ldots,c_n]$，其中 $c_0=0$，且对每个 $1 \le i \le n$：

• 若 $r_i=\mathtt{0}$，则 $c_i=x+c_{i-1}$；
• 若 $r_i=\mathtt{1}$，则 $c_i=y-c_{i-1}$。

此外，我们定义 $f(r)=\sum\limits_{i=1}^n c_i$。

给定一个长度为 $n$ 的不完整二进制字符串 $s$，其中某些字符缺失，用 $\mathtt{?}$ 表示。一个整数 $k$ 被称为“酷”的，当且仅当存在一种方式，将 $s$ 中每个 $\mathtt{?}$ 替换为 $\mathtt{0}$ 或 $\mathtt{1}$，使得 $f(s)=k$。

你的任务是计算所有“酷”整数的和，并对 $998\,244\,353$ 取模。

$^{\text{∗}}$二进制字符串是指每个字符均为 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $x$, and $y$ ($1 \le n \le 10^5$, $1 \le x,y \le 10^6$) — the length of $s$ and the given constants.

The second line contains the incomplete binary string $s$ of length $n$ ($s_i \in {\mathtt{0}, \mathtt{1}, \mathtt{?}}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \le n \le 10^5$，$1 \le x,y \le 10^6$）——分别表示字符串 $s$ 的长度以及给定的常数。

第二行包含一个长度为 $n$ 的不完整二进制字符串 $s$（其中 $s_i \in \{\mathtt{0}, \mathtt{1}, \mathtt{?}\}$）。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single integer — the sum of all cool integers modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——所有酷整数的和对 $998\,244\,353$ 取模的结果。

In the first test case, the string $s$ has already been determined, and its generating array is $[0, 1]$. Thus, $f(s)=1$, and the only cool integer is $1$.

In the third test case, there are four ways to complete the string $s$:

$s$

Generating array

$f(s)$

$\mathtt{000}$

$[0, 7, 14, 21]$

$42$

$\mathtt{001}$

$[0, 7, 14, -9]$

$12$

$\mathtt{100}$

$[0, 5, 12, 19]$

$36$

$\mathtt{101}$

$[0, 5, 12, -7]$

$10$

Thus, the sum of all cool integers is $42+12+36+10=100$.

在第一个测试用例中，字符串 $s$ 已经被确定，其生成数组为 $[0, 1]$。因此，$f(s)=1$，唯一的“酷整数”是 $1$。

在第三个测试用例中，共有四种方式补全字符串 $s$：

$s$

生成数组

$f(s)$

$\mathtt{000}$

$[0, 7, 14, 21]$

$42$

$\mathtt{001}$

$[0, 7, 14, -9]$

$12$

$\mathtt{100}$

$[0, 5, 12, 19]$

$36$

$\mathtt{101}$

$[0, 5, 12, -7]$

$10$

因此，所有“酷整数”的和为 $42+12+36+10=100$。