D - Number of Multisets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

正整数 N, K が与えられます。以下の条件を全て満たす有理数の多重集合は何種類存在しますか？

  • 多重集合の要素数は N で、要素の総和は K
  • 多重集合の要素は全て 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots 、つまり \frac{1}{2^i} (i = 0,1,\dots) のいずれか。

答えは大きくなるかもしれないので、\bmod 998244353 で出力してください。

制約

  • 1 \leq K \leq N \leq 3000
  • 入力される数は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

条件を満たす多重集合の種類数を \bmod 998244353 で出力せよ。

入力例 1

4 2

出力例 1

2

以下の 2 つが条件を満たします。

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

入力例 2

2525 425

出力例 2

687232272

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

2

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