/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
長さ N の整数の集合の列 S=(S_1,S_2,\dots,S_N) のうち、以下の条件を全て満たすものを「素晴らしい集合の列」と呼びます。
- S_i は 1 以上 M 以下の整数のみからなる集合(空集合でもよい)である。(1 \le i \le N)
- S_i と S_{i+1} のうち、ちょうど片方にのみ含まれる要素の個数は 1 個である。(1 \le i \le N-1)
ここで、素晴らしい集合の列 S のスコアを \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
Score : 700 points
Problem Statement
Consider a sequence of integer sets of length N: S=(S_1,S_2,\dots,S_N). We call a sequence brilliant if it satisfies all of the following conditions:
-
S_i is a (possibly empty) integer set, and its elements are in the range [1,M]. (1 \le i \le N)
-
The number of integers that is included in exactly one of S_i and S_{i+1} is 1. (1 \le i \le N-1)
We define the score of a brilliant sequence S as \displaystyle \prod_{i=1}^{M} ( the number of sets among S_1,S_2,\dots,S_N that include i.).
Find, modulo 998244353, the sum of the scores of all possible brilliant sequences.
Constraints
- 1 \le N,M \le 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 3
Sample Output 1
24
Among all possible brilliant sequences, the following 6 have positive scores.
- 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\}
All of them have a score of 4, so the sum of them is 24.
Sample Input 2
12 34
Sample Output 2
786334067