← 返回题目列表

AtCoder · abc276_g

G. 计数序列

中文机器翻译题面 查看原题

分数: 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

这是满足条件的八个序列。

  • (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.