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 翻译