AT_arc185_d [ARC185D] Random Walk on Tree

有一棵包含 $N \times M + 1$ 个顶点的树，顶点编号为 $0, 1, \dots, N \times M$。第 $i$ 条边（$1 \leq i \leq N \times M$）连接顶点 $i$ 和顶点 $\max(i - N, 0)$。 此外，顶点 $0$ 已经被染色，其他顶点尚未染色。 高桥君现在位于顶点 $0$。只要存在未被染色的顶点，他就会重复进行如下操作： - 从当前所在顶点的相邻顶点中，等概率随机选择一个顶点并移动到该顶点。（每次选择都是独立的。）如果当前所在顶点尚未被染色，则将其染色。 请你求出进行操作的次数的期望值，并对 $998244353$ 取模后输出。 期望值 $\bmod\ 998244353$ 的定义：可以证明，所求的期望值一定是有理数。在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时，$Q \not\equiv 0 \pmod{998244353}$ 也成立。此时，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

输入由一行组成，格式如下： > $N$ $M$

请输出进行操作次数的期望值对 $998244353$ 取模后的结果。

### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $N, M$ 均为整数 ### 样例解释 1 高桥君可能按如下方式行动： - 移动到顶点 $1$ 并将其染色。该操作被选择的概率为 $\frac{1}{2}$。 - 移动到顶点 $0$。该操作被选择的概率为 $\frac{1}{2}$。 - 移动到顶点 $1$。该操作被选择的概率为 $\frac{1}{2}$。 - 移动到顶点 $3$ 并将其染色。该操作被选择的概率为 $\frac{1}{2}$。 - 移动到顶点 $1$。该操作被选择的概率为 $1$。 - 移动到顶点 $0$。该操作被选择的概率为 $\frac{1}{2}$。 - 移动到顶点 $2$ 并将其染色。该操作被选择的概率为 $\frac{1}{2}$。 - 移动到顶点 $4$ 并将其染色。该操作被选择的概率为 $\frac{1}{2}$。 高桥君以这种方式行动的概率为 $\frac{1}{128}$，此时操作次数为 $8$。操作次数的期望值为 $20$。 由 ChatGPT 4.1 翻译