#D. D - Number of Multisets

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Score : $600$ points

Problem Statement

You are given two positive integers $N$ and $K$ . How many multisets of rational numbers satisfy all of the following conditions?

The multiset has exactly $N$ elements and the sum of them is equal to $K$ .
Each element of the multiset is one of $1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots$ . In other words, each element can be represented as $\frac{1}{2 ^{i}} (i = 0, 1, \dots)$ .

The answer may be large, so print it modulo $998244353$ .

Constraints

$1 \leq K \leq N \leq 3000$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$

Output

Print the number of multisets of rational numbers that satisfy all of the given conditions modulo $998244353$ .

Sample Input 1

4 2

Sample Output 1

The following two multisets satisfy all of the given conditions:

$1, \frac{1}{2}, \frac{1}{4}, \frac{1}{4}$
$\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}$

Sample Input 2

2525 425

Sample Output 2

687232272

排位赛1

Not Attended

Status: Done
Rule: IOI
Problem: 8
Start at: 2023-7-11 8:00
End at: 2023-7-11 12:00
Duration: 4 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 21

#D. D - Number of Multisets

D - Number of Multisets

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

排位赛1

Status

Development

Support

#D. D - Number of Multisets

D - Number of Multisets

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

排位赛1

Status

Development

Support

Don't have an account?

SIGN IN