CF2150G Counting Is Fun: The Finale

[zabutom, Dubmood - Track Tracking](https://soundcloud.com/zabutom/track-tracking-feat-dubmood) ⠀ You are given three positive integers $ x $ , $ y $ , and $ k $ . You are also given a binary string $ ^{\text{∗}} $ $ a $ ( $ |a| = x + y $ ). Count the number of binary strings $ b $ , modulo $ 998\,244\,353 $ , such that: - there are exactly $ x $ $ \mathtt{0} $ in $ b $ . - there are exactly $ y $ $ \mathtt{1} $ in $ b $ . - there exists an integer $ i $ ( $ 1 \leq i \leq x + y - 1 $ ) such that $ \min \left( f(b_1 b_2 \ldots b_i), f(b_{i+1} b_{i+2} \ldots b_{x+y})\right) \geq k $ , where $ f(s) $ gives the length of the longest non-decreasing subsequence $ ^{\text{†}} $ in $ s $ . - $ b $ is lexicographically larger $ ^{\text{‡}} $ than $ a $ . $ ^{\text{∗}} $ A binary string is a string that only consists of characters $ \mathtt{0} $ and $ \mathtt{1} $ . $ ^{\text{†}} $ A sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements. For example, subsequences of $ \mathtt{1011101} $ are $ \mathtt{0} $ , $ \mathtt{1} $ , $ \mathtt{11111} $ , $ \mathtt{0111} $ , but not $ \mathtt{000} $ nor $ \mathtt{11100} $ . $ ^{\text{‡}} $ A string $ p $ is lexicographically larger than another string $ q $ if and only if one of the following holds: - $ q $ is a prefix of $ p $ , but $ p \ne q $ ; or - in the first position where $ p $ and $ q $ differ, the string $ p $ has a larger element than the corresponding element in $ q $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5000 $ ). The description of the test cases follows. The first line of each test case contains three integers $ x $ , $ y $ , and $ k $ ( $ 1 \le x, y \le 5000 $ , $ 1 \leq k < x + y $ ). The second line of each test case contains a binary string $ a $ ( $ |a| = x+y $ ) consisting of characters $ \mathtt{0} $ and $ \mathtt{1} $ . It is guaranteed that neither the sum of $ x $ nor the sum of $ y $ over all test cases exceeds $ 5000 $ .

For each test case, output an integer on a new line, the number of binary strings that satisfy the conditions modulo $ 998\,244\,353 $ .

For the first test case, there are two valid strings: $ \mathtt{01} $ and $ \mathtt{10} $ . For the third test case, there are four valid strings: $ \mathtt{0110} $ , $ \mathtt{1001} $ , $ \mathtt{1010} $ , and $ \mathtt{1100} $ .