← 返回题目列表

AtCoder · arc147_d

D. 设置分数

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

分数: 700 点

问题陈述

考虑长度为整数的序列 N: S=(S_1,S_2,\dots,S_N)。 我们称一个序列为 辉煌 如果满足以下所有条件:

  • S_i 是一个(可能为空)整数集,其元素在范围内 [1,M]. (1 \le i \le N)

  • 恰好包含在以下之一中的整数数量 S_i 和 S_{i+1} is 1. (1 \le i \le N-1)

我们定义精彩序列的分数 S as \displaystyle \prod_{i=1}^{M} ( 其中的套数 S_1,S_2,\dots,S_N 包括 i.).

查找,取模 998244353,所有可能的精彩序列的分数总和。

约束

  • 1 \le N,M \le 2 \times 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M

输出

打印答案。


示例输入 1

2 3

示例输出 1

24

在所有可能的精彩序列中,以下 6 得分为正。

  • S_1=\{1,2\},S_2=\{1,2,3\}
  • S_1=\{1,3\},S_2=\{1,2,3\}
  • S_1=\{2,3\},S_2=\{1,2,3\}
  • S_1=\{1,2,3\},S_2=\{1,2\}
  • S_1=\{1,2,3\},S_2=\{1,3\}
  • S_1=\{1,2,3\},S_2=\{2,3\}

他们的得分均为 4,所以它们的总和是 24.


示例输入 2

12 34

示例输出 2

786334067