/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
頂点に 0 から NM の番号がついている NM+1 頂点の木があります。i(1 \le i \le NM) 本目の辺は頂点 i と頂点 \max(i-N,0) を結ぶ辺です。
最初、頂点 i は色 i \bmod N で塗られています。あなたは以下の操作を 0 回以上行うことが出来ます。
- 辺で結ばれている 2 頂点 u,v を選ぶ。u の色を v の色に塗り替える。
操作後の木としてあり得るものの個数を 998244353 で割ったあまりを求めてください。ただし、2 つの木はある頂点の色が違うときに区別します。
制約
- 1 \le N,M \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 1
出力例 1
42
例えば、操作列として以下のようなものが考えられます。このケースを含め、最終的にあり得る木としては 42 通りがあります。
入力例 2
4 2
出力例 2
219100
入力例 3
20 24
出力例 3
984288778
入力例 4
123456 112233
出力例 4
764098676
Score: 1000 points
Problem Statement
There is a tree with NM+1 vertices numbered 0 to NM. The i-th edge (1 \le i \le NM) connects vertices i and \max(i-N,0).
Initially, vertex i is colored with color i \bmod N. You can perform the following operation zero or more times:
- Choose two vertices u and v connected by an edge. Repaint the color of vertex u with that of vertex v.
Find the number, modulo 998244353, of possible trees after the operations. Two trees are distinguished if and only if some vertex has different colors.
Constraints
- 1 \le N, M \le 2 \times 10^5
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
3 1
Sample Output 1
42
One possible sequence of operations is as follows. Including this one, there are 42 possible final trees.
Sample Input 2
4 2
Sample Output 2
219100
Sample Input 3
20 24
Sample Output 3
984288778
Sample Input 4
123456 112233
Sample Output 4
764098676