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

Input

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

Output

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

Note

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

Counting Is Fun: The Finale

Examples