D. Cool Problem
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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}$$$.

Input

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$$$.

Output

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

Example
Input
4
1 1 2
0
1 1 2
?
3 7 5
?0?
7 114514 191981
?1?????
Output
1
3
100
8039591
Note

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$$$.