311009: CF1920E. Counting Binary Strings

E. Counting Binary Stringstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Patrick calls a substring$^\dagger$ of a binary string$^\ddagger$ good if this substring contains exactly one 1.

Help Patrick count the number of binary strings $s$ such that $s$ contains exactly $n$ good substrings and has no good substring of length strictly greater than $k$. Note that substrings are differentiated by their location in the string, so if $s =$ 1010 you should count both occurrences of 10.

$^\dagger$ A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$^\ddagger$ A binary string is a string that only contains the characters 0 and 1.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2500$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $n$ and $k$ ($1 \leq n \leq 2500$, $1 \leq k \leq n$) — the number of required good substrings and the maximum allowed length of a good substring.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2500$.

Output

For each test case, output a single integer — the number of binary strings $s$ such that $s$ contains exactly $n$ good substrings and has no good substring of length strictly greater than $k$. Since this integer can be too large, output it modulo $998\,244\,353$.

ExampleInput

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

Output

1
3
5
12
9
259280854

Note

In the first test case, the only suitable binary string is 1. String 01 is not suitable because it contains a substring 01 with length $2 > 1$.

In the second test case, suitable binary strings are 011, 110 and 111.

In the third test case, suitable binary strings are 101, 0110, 0111, 1110, and 1111.

题目大意：
这个题目是关于计算特定条件的二进制字符串的数量。一个二进制字符串是一个只包含字符 '0' 和 '1' 的字符串。如果一个二进制字符串的子串中恰好只有一个 '1'，则称这个子串是“好的”。需要帮助Patrick计算有多少个二进制字符串 s，使得 s 包含恰好 n 个好的子串，并且没有长度严格大于 k 的好的子串。子串根据在字符串中的位置来区分，例如，如果 s = 1010，那么应该计算 10 的两个出现次数。

输入输出数据格式：
输入：
- 输入包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 2500) — 测试用例的数量。
- 每个测试用例只有一行，包含两个整数 n 和 k (1 ≤ n ≤ 2500, 1 ≤ k ≤ n) — 所需的好子串的数量和允许的好子串的最大长度。
- 保证所有测试用例中 n 的总和不超过 2500。

输出：
- 对于每个测试用例，输出一个整数 — 包含恰好 n 个好子串并且没有长度严格大于 k 的好子串的二进制字符串 s 的数量。由于这个整数可能非常大，输出它模 998,244,353 的结果。

示例输入输出：
输入：
```
6
1 1
3 2
4 2
5 4
6 2
2450 2391
```
输出：
```
1
3
5
12
9
259280854
```

注意：
- 在第一个测试用例中，唯一合适的二进制字符串是 1。字符串 01 不合适，因为它包含一个长度为 2 > 1 的子串 01。
- 在第二个测试用例中，合适的二进制字符串是 011、110 和 111。
- 在第三个测试用例中，合适的二进制字符串是 101、0110、0111、1110 和 1111。题目大意： 这个题目是关于计算特定条件的二进制字符串的数量。一个二进制字符串是一个只包含字符 '0' 和 '1' 的字符串。如果一个二进制字符串的子串中恰好只有一个 '1'，则称这个子串是“好的”。需要帮助Patrick计算有多少个二进制字符串 s，使得 s 包含恰好 n 个好的子串，并且没有长度严格大于 k 的好的子串。子串根据在字符串中的位置来区分，例如，如果 s = 1010，那么应该计算 10 的两个出现次数。 输入输出数据格式： 输入： - 输入包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 2500) — 测试用例的数量。 - 每个测试用例只有一行，包含两个整数 n 和 k (1 ≤ n ≤ 2500, 1 ≤ k ≤ n) — 所需的好子串的数量和允许的好子串的最大长度。 - 保证所有测试用例中 n 的总和不超过 2500。 输出： - 对于每个测试用例，输出一个整数 — 包含恰好 n 个好子串并且没有长度严格大于 k 的好子串的二进制字符串 s 的数量。由于这个整数可能非常大，输出它模 998,244,353 的结果。 示例输入输出： 输入： ``` 6 1 1 3 2 4 2 5 4 6 2 2450 2391 ``` 输出： ``` 1 3 5 12 9 259280854 ``` 注意： - 在第一个测试用例中，唯一合适的二进制字符串是 1。字符串 01 不合适，因为它包含一个长度为 2 > 1 的子串 01。 - 在第二个测试用例中，合适的二进制字符串是 011、110 和 111。 - 在第三个测试用例中，合适的二进制字符串是 101、0110、0111、1110 和 1111。