D. Классная задача
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны две целочисленные константы $$$x$$$ и $$$y$$$.

Для бинарной$$$^{\text{∗}}$$$ строки $$$r$$$ длины $$$n$$$ определим её генерирующий массив как массив $$$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$$$ называется классным, если и только если существует способ заменить каждый $$$\mathtt{?}$$$ в $$$s$$$ либо на $$$\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$$$ и заданные константы.

Вторая строка содержит неполную бинарную строку $$$s$$$ длины $$$n$$$ ($$$s_i \in \{\mathtt{0}, \mathtt{1}, \mathtt{?}\}$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сумму всех классных целых чисел по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
1 1 2
0
1 1 2
?
3 7 5
?0?
7 114514 191981
?1?????
Выходные данные
1
3
100
8039591
Примечание

В первом наборе входных данных строка $$$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$$$.