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

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

Cool Problem

Examples