分数: 800 点
问题陈述
有一棵树 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.
期望值模是多少 998244353?
可以证明,所求的期望值总是有理数。在这个问题的约束下,当该值表示为不可约分数时 \frac{P}{Q},还可以证明 Q \not\equiv 0 \pmod{998244353}。那么,唯一存在一个整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353。报告此事 R.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N 和 M 是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印他执行该操作的预期次数,取模 998244353.
示例输入 1
2 2
示例输出 1
20
例如,Takahashi 的行为如下。
- 移动到顶点 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.
示例输入 2
123456 185185
示例输出 2
69292914