D - Sequence 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 3 点

問題文

M 以下の非負整数からなる長さ N の整数列 A=(a_1,a_2,\dots,a_N) であって、次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • A を昇順にソートした列を B=(b_1,b_2,\dots,b_N) とする。この時、 1 \leq i \leq N-1 を満たす i 全てについて b_i と b_{i+1} の偶奇が異なる。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N, M は整数

入力

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

N M

出力

答えを出力せよ。

入力例 1

2 3

出力例 1

8

条件を満たす数列は次の 8 個です。

  • (0,1)
  • (0,3)
  • (1,0)
  • (1,2)
  • (2,1)
  • (2,3)
  • (3,0)
  • (3,2)

入力例 2

12345 67890

出力例 2

761484871

Score: 3 points

Problem Statement

Consider integer sequences A=(a_1,a_2,\dots,a_N) of length N, where each element is a non-negative integer not greater than M.
Count how many such sequences satisfy the following condition, and output the result modulo 998244353.

  • Let B=(b_1,b_2,\dots,b_N) be the sequence obtained by sorting A in ascending order.
    For every i such that 1 \leq i \leq N-1, the parity of b_i and b_{i+1} must be different.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N, M are integers

Input

The input is given from standard input in the following format:

N M

Output

Print the answer.

Sample Input 1

2 3

Sample Output 1

8

There are 8 sequences that satisfy the condition:

  • (0,1)
  • (0,3)
  • (1,0)
  • (1,2)
  • (2,1)
  • (2,3)
  • (3,0)
  • (3,2)

Sample Input 2

12345 67890

Sample Output 2

761484871