G - Count Sequences Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

以下の条件を満たす項数 N の整数列 A=(a_1,a_2,\ldots,a_N) の個数を 998244353 で割った余りを求めてください。

  • 0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M
  • i=1,2,\ldots,N-1 それぞれについて、「a_i を 3 で割った余り」と「a_{i+1} を 3 で割った余り」が異なる

制約

  • 2 \leq N \leq 10^7
  • 1 \leq M \leq 10^7
  • 入力はすべて整数

入力

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

N M

出力

答えを出力せよ。

入力例 1

3 4

出力例 1

8

以下の 8 個が条件を満たします。

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

入力例 2

276 10000000

出力例 2

909213205

個数を 998244353 で割った余りを求めてください。

Score : 600 points

Problem Statement

Find the number of sequences of integers with N terms, A=(a_1,a_2,\ldots,a_N), that satisfy the following conditions, modulo 998244353.

  • 0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M.
  • For each i=1,2,\ldots,N-1, the remainder when a_i is divided by 3 is different from the remainder when a_{i+1} is divided by 3.

Constraints

  • 2 \leq N \leq 10^7
  • 1 \leq M \leq 10^7
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

3 4

Sample Output 1

8

Here are the eight sequences that satisfy the conditions.

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

Sample Input 2

276 10000000

Sample Output 2

909213205

Be sure to find the count modulo 998244353.