CF2150G Counting Is Fun: The Finale

[zabutom, Dubmood - Track Tracking](https://soundcloud.com/zabutom/track-tracking-feat-dubmood) ⠀ 给定三个正整数 $x$、$y$ 和 $k$。 同时给定一个二进制字符串 $a$（$|a| = x + y$）。 请计算满足下列条件的二进制字符串 $b$ 的个数，结果对 $998\,244\,353$ 取模： - $b$ 中恰好有 $x$ 个 $0$。 - $b$ 中恰好有 $y$ 个 $1$。 - 存在一个整数 $i$（$1 \leq i \leq x + y - 1$），使得 $\min \left( f(b_1 b_2 \ldots b_i), f(b_{i+1} b_{i+2} \ldots b_{x+y})\right) \geq k$，其中 $f(s)$ 表示字符串 $s$ 的最长不下降子序列的长度。 - $b$ 的字典序大于 $a$。 【注：】 $^*$ 二进制字符串指只由字符 $0$ 和 $1$ 组成的字符串。 $^\dagger$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可以通过删除 $b$ 的若干（可以为零或全部）元素得到。例如，$\mathtt{1011101}$ 的子序列有 $\mathtt{0}$、$\mathtt{1}$、$\mathtt{11111}$、$\mathtt{0111}$，但没有 $\mathtt{000}$ 和 $\mathtt{11100}$。 $^\ddagger$ 如果字符串 $p$ 满足以下条件之一被称为字典序大于字符串 $q$： - $q$ 是 $p$ 的前缀，且 $p \ne q$； - 在 $p$ 和 $q$ 第一个不同的位置，$p$ 的该字符比 $q$ 的该字符大。

每组测试包含多组测试用例。第一行包含整数 $t$（$1 \le t \le 5000$），表示测试用例数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含三个整数 $x$、$y$ 和 $k$（$1 \le x, y \le 5000$，$1 \leq k < x + y$）。 每组测试用例的第二行包含一个长度为 $x+y$ 的二进制字符串 $a$，仅包含字符 $0$ 和 $1$。 保证所有测试用例中 $x$ 的和不超过 $5000$，$y$ 的和也不超过 $5000$。

对于每组测试用例，输出一个整数，表示满足条件的二进制字符串数量，对 $998\,244\,353$ 取模。

对于第一个测试用例，有两个满足条件的字符串：$\mathtt{01}$ 和 $\mathtt{10}$。 对于第三个测试用例，有四个满足条件的字符串：$\mathtt{0110}$、$\mathtt{1001}$、$\mathtt{1010}$ 和 $\mathtt{1100}$。 由 ChatGPT 5 翻译