write a go solution for Description:
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 textttP, textttS, and texttt?.

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

- If s_i=textttP, b_i is the sum of a_1 through a_i.
- If s_i=textttS, b_i is the sum of a_i through a_n.

Output the number of ways to replace all texttt? in s with either textttP or textttS 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 Format:
The first line contains a single integer t (1<=t<=10^3) — the number of test cases.

The first line of each test case contains two integers n and m (2<=n<=2*10^3, 2<=m<=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 textttP, textttS, and texttt?.

The third line of each test case contains n integers b_1,b_2,ldots,b_n (|b_i|<=m*n).

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

Output Format:
For each test case, output a single integer — the number of ways to replace all texttt? in s with either textttP or textttS 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:

1. textttP — [colorredtextbf1,3,4,2]: sum of 1.
2. textttS — [1,colorredtextbf3,4,2]: sum of 9.
3. textttP — [colorred1,3,textbf4,2]: sum of 8.
4. textttP — [colorred1,3,4,textbf2]: sum of 10.

In the second test case, it can be shown that no array a with all |a_i|<=m=10^9 satisfies all constraints.. Output only the code with no comments, explanation, or additional text.