有一个隐藏数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$,其元素是 $$$-m$$$ 和 $$$m$$$(含)之间的整数。
给定一个长度为 $$$n$$$ 的数组 $$$b_1, b_2, \ldots, b_n$$$ 和一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中包含字符 $$$\texttt{P}$$$、$$$\texttt{S}$$$ 和 $$$\texttt{?}$$$。
对于从 $$$1$$$ 到 $$$n$$$(含)的每个 $$$i$$$,我们必须:
- 如果 $$$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$$$ 满足下式给出的约束数组$$$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$$$ 的最大绝对值。
每个测试用例的第二行包含一个长度为 $$$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
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
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$$$ 满足所有约束。