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$.

见题面 Input 部分

见题面 Output 部分

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

1. $\texttt{P}$ — ${[\color{red}{\textbf{1}},3,4,2]}$: sum of $1$.
2. $\texttt{S}$ — ${[1,\color{red}{\textbf{3},4,2}]}$: sum of $9$.
3. $\texttt{P}$ — ${[\color{red}{1,3,\textbf{4}},2]}$: sum of $8$.
4. $\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.