CF1984F.Reconstruction

有一个长度为 $n$ 的隐藏数组 $a_1, a_2, \ldots, a_n$，其中每个元素都是 $-m$ 到 $m$ 之间的整数（包含端点）。

你会得到一个长度为 $n$ 的数组 $b_1, b_2, \ldots, b_n$ 和一个长度为 $n$ 的字符串 $s$，其中 $s$ 由字符 $\texttt{P}$、$\texttt{S}$ 和 $\texttt{?}$ 组成。

对于每个 $i$（$1 \leq i \leq n$），必须满足：

• 如果 $s_i = \texttt{P}$，则 $b_i$ 是 $a_1$ 到 $a_i$ 的前缀和。
• 如果 $s_i = \texttt{S}$，则 $b_i$ 是 $a_i$ 到 $a_n$ 的后缀和。

请输出有多少种方法可以将 $s$ 中所有的 $\texttt{?}$ 替换为 $\texttt{P}$ 或 $\texttt{S}$，使得存在一个满足所有约束条件的数组 $a_1, a_2, \ldots, a_n$，且每个元素的绝对值不超过 $m$。

由于答案可能很大，请输出对 $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$ 的长度和每个元素的最大绝对值。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{P}$、$\texttt{S}$ 和 $\texttt{?}$ 组成。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$|b_i| \leq m \cdot n$）。

所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^3$。

对于每个测试用例，输出一个整数，表示有多少种方法将 $s$ 中所有的 $\texttt{?}$ 替换为 $\texttt{P}$ 或 $\texttt{S}$，使得存在一个满足所有约束条件的数组 $a_1, a_2, \ldots, a_n$，对 $998\,244\,353$ 取模。

在第一个测试用例中，可以发现如下数组满足所有约束，因此答案为 $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_i| \leq m = 10^9$ 的数组 $a$ 满足所有约束。

由 ChatGPT 4.1 翻译