G. Counting Is Fun: The Finale
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
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$$$.

Example
Input
6
1 1 1
00
2 2 2
1110
2 2 1
0101
1 6 3
0000000
4 6 4
0010110010
10 6 7
0010110000101100
Output
2
0
4
7
106
203
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}$$$.