给定三个正整数 $$$x$$$、$$$y$$$ 和 $$$k$$$。
还给你一个二进制字符串$$$^{\text{*}}$$$ $$$a$$$ ($$$|a| = x + y$$$)。
计算二进制字符串 $$$b$$$ 的数量,以 $$$998\,244\,353$$$ 为模,这样:
- $$$b$$$ 中正好有 $$$x$$$ $$$\mathtt{0}$$$。
- $$$b$$$ 中正好有 $$$y$$$ $$$\mathtt{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$$$ 中最长非递减子序列$$$^{\text{†}}$$$ 的长度。
- $$$b$$$ 按字典顺序比 $$$a$$$ 更大$$$^{\text{‡}}$$$。
$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串。
$$$^{\text{†}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。例如,$$$\mathtt{1011101}$$$ 的子序列是 $$$\mathtt{0}$$$、$$$\mathtt{1}$$$、$$$\mathtt{11111}$$$、$$$\mathtt{0111}$$$,但不是 $$$\mathtt{000}$$$ 也不是$$$\mathtt{11100}$$$。
$$$^{\text{‡}}$$$当且仅当满足以下条件之一时,字符串 $$$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 \lt x + y$$$)。
每个测试用例的第二行包含一个二进制字符串 $$$a$$$ ($$$|a| = x+y$$$),由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。
保证所有测试用例的 $$$x$$$ 总和和 $$$y$$$ 总和都不超过 $$$5000$$$。
输出
对于每个测试用例,在新行输出一个整数,满足条件的二进制字符串的数量以 $$$998\,244\,353$$$ 为模。
示例
输入复制
61 1 1002 2 211102 2 101011 6 300000004 6 4001011001010 6 70010110000101100
输出复制
2047106203
注意
对于第一个测试用例,有两个有效字符串:$$$\mathtt{01}$$$ 和 $$$\mathtt{10}$$$。
对于第三个测试用例,有四个有效字符串:$$$\mathtt{0110}$$$、$$$\mathtt{1001}$$$、$$$\mathtt{1010}$$$ 和 $$$\mathtt{1100}$$$。