CF1984F Reconstruction

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

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

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

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.