有两个整数常量 $$$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$$$。
给你一个不完整的二进制字符串$$$s$$$,长度为$$$n$$$,其中缺少一些字符,用$$$\mathtt{?}$$$表示。整数 $$$k$$$ 被称为 酷 当且仅当存在一种方法将 $$$s$$$ 中的每个 $$$\mathtt{?}$$$ 替换为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$,使得 $$$f(s)=k$$$。
你的任务是计算所有的总和 酷 整数,以 $$$998\,244\,353$$$ 为模。
$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 所有测试用例的总和 酷 以 $$$998\,244\,353$$$ 为模的整数。
示例
输入复制
41 1 201 1 2?3 7 5?0?7 114514 191981?1?????
输出复制
131008039591
注意
在第一个测试用例中,字符串 $$$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$$$。