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