AT_arc176_f.[ARC176F] Colorful Star

有一棵包含 $NM+1$ 个顶点的树，顶点编号为 $0$ 到 $NM$。第 $i$ 条边（$1 \le i \le NM$）连接顶点 $i$ 和顶点 $\max(i-N,0)$。

最初，顶点 $i$ 被染成颜色 $i \bmod N$。你可以进行如下操作任意多次（可以为 $0$ 次）：

• 选择通过一条边相连的两个顶点 $u,v$，将 $u$ 的颜色改为 $v$ 的颜色。

请你求出，经过若干次操作后，所有可能的树的方案数，答案对 $998244353$ 取模。注意，如果某个顶点的颜色不同，则认为是不同的树。

输入包含一行：

$N$ $M$

输出答案。

限制

• $1 \le N, M \le 2 \times 10^5$

样例解释 1

例如，可以考虑如下的操作序列。在包括这种情况在内，最终可能的树共有 $42$ 种。

由 ChatGPT 4.1 翻译