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