F. Реконструкция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется секретный массив $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$, элементами которого являются целые числа от $$$-m$$$ до $$$m$$$ включительно.

Даны массивы $$$b_1, b_2, \ldots, b_n$$$ длины $$$n$$$ и строка $$$s$$$ длины $$$n$$$, состоящая из символов $$$\texttt{P}$$$, $$$\texttt{S}$$$ и $$$\texttt{?}$$$.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ включительно, должно выполняться следующее:

  • Если $$$s_i = \texttt{P}$$$, то $$$b_i$$$ — это сумма элементов с $$$a_1$$$ по $$$a_i$$$.
  • Если $$$s_i = \texttt{S}$$$, то $$$b_i$$$ — это сумма элементов с $$$a_i$$$ по $$$a_n$$$.

Выведите количество способов заменить все $$$\texttt{?}$$$ в $$$s$$$ на $$$\texttt{P}$$$ или $$$\texttt{S}$$$ так, чтобы существовал массив $$$a_1, a_2, \ldots, a_n$$$ с элементами, не превышающими $$$m$$$ по абсолютному значению, удовлетворяющий ограничениям, заданным массивом $$$b_1, b_2, \ldots, b_n$$$ и строкой $$$s$$$.

Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^3$$$, $$$2 \leq m \leq 10^{9}$$$) — длина секретного массива $$$a_1, a_2, \ldots, a_n$$$ и максимальное абсолютное значение элемента $$$a_i$$$.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов $$$\texttt{P}$$$, $$$\texttt{S}$$$ и $$$\texttt{?}$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$|b_i| \leq m \cdot n$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^3$$$.

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

Для каждого набора входных данных выведите одно целое число — количество способов заменить все $$$\texttt{?}$$$ в $$$s$$$ на $$$\texttt{P}$$$ или $$$\texttt{S}$$$, которые приводят к существованию допустимого массива $$$a_1, a_2, \ldots, a_n$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
6
4 10
PSPP
1 9 8 10
4 1000000000
????
1 1 1 4000000000
8 1000000000
?P?SSP?P
-857095623 -1424391899 -851974476 673437144 471253851 -543483033 364945701 -178537332
4 7
PPSS
4 2 1 3
9 20
?????????
1 2 3 4 5 6 7 8 9
3 1000000000
P??
-145463248 -974068460 -1287458396
Выходные данные
1
0
2
1
14
1
Примечание

В первом наборе входных данных мы видим, что следующий массив удовлетворяет всем ограничениям, поэтому ответ — $$$1$$$:

  1. $$$\texttt{P}$$$ — $$${[\color{red}{\textbf{1}},3,4,2]}$$$: сумма $$$1$$$.
  2. $$$\texttt{S}$$$ — $$${[1,\color{red}{\textbf{3},4,2}]}$$$: сумма $$$9$$$.
  3. $$$\texttt{P}$$$ — $$${[\color{red}{1,3,\textbf{4}},2]}$$$: сумма $$$8$$$.
  4. $$$\texttt{P}$$$ — $$${[\color{red}{1,3,4,\textbf{2}}]}$$$: сумма $$$10$$$.

Во втором наборе входных данных можно показать, что ни один массив $$$a$$$ со всеми $$$|a_i| \leq m = 10^9$$$ не удовлетворяет ограничениям.