Bin

Time limit15sMemory limit512 MB

Summary

Count full binary trees with n leaves where each node's left leaf count exceeds its right leaf count by at most k, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Divide and conquer
Solved: No attempts yet

Statement

Find the number of full binary trees (every vertex has 0 or 2 children) with $n$ leaves such that, for every vertex with two children, the number of leaves in its left subtree does not exceed the number of leaves in its right subtree by more than $k$ . Print the answer modulo 998244353.

Input and output

The only line contains two integers $n$ and $k$ ( $2 \le n \le 10^6$ , $0 \le k \le 100$ ).

Print the required number.

Examples3

Example 1
Input
```
2 0
```
Expected output
```
1
```
Example 2
Input
```
3 0
```
Expected output
```
1
```
Example 3
Input
```
3 1
```
Expected output
```
2
```