There is a hidden array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$ whose elements are integers between $$$-m$$$ and $$$m$$$, inclusive.

You are given an array $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ and a string $$$s$$$ of length $$$n$$$ consisting of the characters $$$\texttt{P}$$$, $$$\texttt{S}$$$, and $$$\texttt{?}$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$ inclusive, we must have:

If $$$s_i = \texttt{P}$$$, $$$b_i$$$ is the sum of $$$a_1$$$ through $$$a_i$$$.
If $$$s_i = \texttt{S}$$$, $$$b_i$$$ is the sum of $$$a_i$$$ through $$$a_n$$$.

Output the number of ways to replace all $$$\texttt{?}$$$ in $$$s$$$ with either $$$\texttt{P}$$$ or $$$\texttt{S}$$$ such that there exists an array $$$a_1, a_2, \ldots, a_n$$$ with elements not exceeding $$$m$$$ by absolute value satisfying the constraints given by the array $$$b_1, b_2, \ldots, b_n$$$ and the string $$$s$$$.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^3$$$, $$$2 \leq m \leq 10^{9}$$$) — the length of the hidden array $$$a_1, a_2, \ldots, a_n$$$ and the maximum absolute value of an element $$$a_i$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{P}$$$, $$$\texttt{S}$$$, and $$$\texttt{?}$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$|b_i| \leq m \cdot n$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

Output

For each test case, output a single integer — the number of ways to replace all $$$\texttt{?}$$$ in $$$s$$$ with either $$$\texttt{P}$$$ or $$$\texttt{S}$$$ that result in the existence of a valid array $$$a_1, a_2, \ldots, a_n$$$, modulo $$$998\,244\,353$$$.

Note

In the first test case, we can see that the following array satisfies all constraints, thus the answer is $$$1$$$:

$$$\texttt{P}$$$ — $$${[\color{red}{\textbf{1}},3,4,2]}$$$: sum of $$$1$$$.
$$$\texttt{S}$$$ — $$${[1,\color{red}{\textbf{3},4,2}]}$$$: sum of $$$9$$$.
$$$\texttt{P}$$$ — $$${[\color{red}{1,3,\textbf{4}},2]}$$$: sum of $$$8$$$.
$$$\texttt{P}$$$ — $$${[\color{red}{1,3,4,\textbf{2}}]}$$$: sum of $$$10$$$.

In the second test case, it can be shown that no array $$$a$$$ with all $$$|a_i| \leq m = 10^9$$$ satisfies all constraints.

Reconstruction

Examples