D - I Wanna Win The Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N , M が与えられます。 長さ N の整数列 A であって、以下の条件を満たすものの数を答えてください。

  • 0 \leq A_i \left(i = 1, 2, \ldots, N\right)
  • \sum_{i = 1}^{N} A_i = M
  • A_1 xor A_2 xor \cdots xor A_N = 0 （ここで xor はビットごとの排他的論理和を表す）

ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを答えてください。

制約

  • 入力は全て整数
  • 1 \leq N \leq 5000
  • 1 \leq M \leq 5000

入力

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

N M

出力

答えを出力せよ。

入力例 1

5 20

出力例 1

475

条件を満たす数列 A として、例えば以下のようなものが考えられます。

  • A = \left(10, 0, 10, 0, 0\right)
  • A = \left(1, 2, 3, 7, 7\right)

入力例 2

10 5

出力例 2

0

入力例 3

3141 2718

出力例 3

371899128

Score : 500 points

Problem Statement

Given are integers N and M. How many sequences A of N integers satisfy the following conditions?

  • 0 \leq A_i \left(i = 1, 2, \ldots, N\right)
  • \sum_{i = 1}^{N} A_i = M
  • A_1 xor A_2 xor \cdots xor A_N = 0 ("xor" denotes the bitwise XOR.)

Since the answer can be enormous, report it modulo 998244353.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 5000
  • 1 \leq M \leq 5000

Input

Input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

5 20

Sample Output 1

475

Some of the sequences A satisfying the conditions follow:

  • A = \left(10, 0, 10, 0, 0\right)
  • A = \left(1, 2, 3, 7, 7\right)

Sample Input 2

10 5

Sample Output 2

0

Sample Input 3

3141 2718

Sample Output 3

371899128