G. Counting Is Fun: The Finaletime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputzabutom, Dubmood - Track Tracking⠀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$$$. InputEach 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$$$.OutputFor each test case, output an integer on a new line, the number of binary strings that satisfy the conditions modulo $$$998\,244\,353$$$.ExampleInput61 1 1002 2 211102 2 101011 6 300000004 6 4001011001010 6 70010110000101100Output2047106203NoteFor 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}$$$.