Имеется секретный массив \(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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество способов заменить все \(\texttt{?}\) в \(s\) на \(\texttt{P}\) или \(\texttt{S}\), которые приводят к существованию допустимого массива \(a_1, a_2, \ldots, a_n\), по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных мы видим, что следующий массив удовлетворяет всем ограничениям, поэтому ответ — \(1\):
- \(\texttt{P}\) — \({[\color{red}{\textbf{1}},3,4,2]}\): сумма \(1\).
- \(\texttt{S}\) — \({[1,\color{red}{\textbf{3},4,2}]}\): сумма \(9\).
- \(\texttt{P}\) — \({[\color{red}{1,3,\textbf{4}},2]}\): сумма \(8\).
- \(\texttt{P}\) — \({[\color{red}{1,3,4,\textbf{2}}]}\): сумма \(10\).
Во втором наборе входных данных можно показать, что ни один массив \(a\) со всеми \(|a_i| \leq m = 10^9\) не удовлетворяет ограничениям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|