← 返回题目列表

Codeforces · 1920/E

E. 计算二进制字符串

中文机器翻译题面 查看原题

如果二进制字符串 $$$^\ddagger$$$ 的子字符串 $$$^\dagger$$$ 正好包含一个 1,则 Patrick 称此子字符串为好。

帮助 Patrick 计算二进制字符串 $$$s$$$ 的数量,使得 $$$s$$$ 恰好包含 $$$n$$$ 好子串,并且没有长度严格大于 $$$k$$$ 的好子串。请注意,子字符串根据其在字符串中的位置进行区分,因此如果 $$$s =$$$ 1010,则应计算 10 的两次出现。

$$$^\dagger$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

$$$^\ddagger$$$ 二进制字符串是只包含字符 0 和 1 的字符串。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — 所需的好子串的数量和好子串的最大允许长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2500$$$。

输出

对于每个测试用例,输出一个整数 - 二进制字符串 $$$s$$$ 的数量,使得 $$$s$$$ 恰好包含 $$$n$$$ 好子串,并且没有长度严格大于 $$$k$$$ 的好子串。由于该整数可能太大,因此输出它对 $$$998\,244\,353$$$ 取模。

示例

输入 #1

6
1 1
3 2
4 2
5 4
6 2
2450 2391

输出 #1

1
3
5
12
9
259280854

注意

在第一个测试用例中,唯一合适的二进制字符串是 1。字符串 01 不合适,因为它包含长度 $$$2 > 1$$$ 的子字符串 01。

在第二个测试用例中,合适的二进制字符串是 011、110 和 111。

在第三个测试用例中,合适的二进制字符串是 101、0110、0111、1110 和 1111。