CF2187D Cool Problem

There are two integer constants $ x $ and $ y $ . For a binary $ ^{\text{∗}} $ string $ r $ of length $ n $ , we define its generating array as an array $ c=[c_0,c_1,\ldots,c_n] $ such that $ c_0=0 $ , and for each $ 1 \le i \le n $ : - If $ r_i=\mathtt{0} $ , then $ c_i=x+c_{i-1} $ ; - If $ r_i=\mathtt{1} $ , then $ c_i=y-c_{i-1} $ . Additionally, we define $ f(r)=\sum\limits_{i=1}^n c_i $ . You are given an incomplete binary string $ s $ of length $ n $ , where some characters in it are missing, represented by $ \mathtt{?} $ . An integer $ k $ is called cool if and only if there exists a way to replace each $ \mathtt{?} $ in $ s $ with either $ \mathtt{0} $ or $ \mathtt{1} $ , such that $ f(s)=k $ . Your task is to calculate the sum of all cool integers, modulo $ 998\,244\,353 $ . $ ^{\text{∗}} $ A binary string is a string where each character is either $ \mathtt{0} $ or $ \mathtt{1} $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ x $ , and $ y $ ( $ 1 \le n \le 10^5 $ , $ 1 \le x,y \le 10^6 $ ) — the length of $ s $ and the given constants. The second line contains the incomplete binary string $ s $ of length $ n $ ( $ s_i \in \{\mathtt{0}, \mathtt{1}, \mathtt{?}\} $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

For each test case, output a single integer — the sum of all cool integers modulo $ 998\,244\,353 $ .

In the first test case, the string $ s $ has already been determined, and its generating array is $ [0, 1] $ . Thus, $ f(s)=1 $ , and the only cool integer is $ 1 $ . In the third test case, there are four ways to complete the string $ s $ : $ s $ Generating array $ f(s) $ $ \mathtt{000} $ $ [0, 7, 14, 21] $ $ 42 $ $ \mathtt{001} $ $ [0, 7, 14, -9] $ $ 12 $ $ \mathtt{100} $ $ [0, 5, 12, 19] $ $ 36 $ $ \mathtt{101} $ $ [0, 5, 12, -7] $ $ 10 $ Thus, the sum of all cool integers is $ 42+12+36+10=100 $ .