{"problem":{"name":"Random Walk on Tree","description":{"content":"There is a tree with $N \\times M + 1$ vertices numbered $0, 1, \\dots, N \\times M$. The $i$\\-th edge $(1 \\leq i \\leq N \\times M)$ connects vertices $i$ and $\\max(i - N, 0)$.   Vertex $0$ is painted. Th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc185_d"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N \\times M + 1$ vertices numbered $0, 1, \\dots, N \\times M$. The $i$\\-th edge $(1 \\leq i \\leq N \\times M)$ connects vertices $i$ and $\\max(i - N, 0)$.  \nVertex $0$ is painted. The other vertices are unpainted.  \nTakahashi is at vertex $0$. As long as there exists an unpainted vertex, he performs the following operation:\n\n*   He chooses one of the vertices adjacent to his current vertex uniformly at random (all choices are independent) and moves to that vertex. Then, if the vertex he is on is unpainted, he paints it.\n\nFind the expected number of times he performs the operation, modulo $998244353$.\nWhat is the expected value modulo $998244353$?It can be proved that the sought expected value is always rational. Under the constraints of this problem, when that value is expressed as an irreducible fraction $\\frac{P}{Q}$, it can also be proved that $Q \\not\\equiv 0 \\pmod{998244353}$. Then, there uniquely exists an integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R \\lt 998244353$. Report this $R$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $N$ and $M$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc185_d","tags":[],"sample_group":[["2 2","20\n\nFor example, Takahashi could behave as follows.\n\n*   Moves to vertex $1$ and paints it. This action is chosen with probability $\\frac{1}{2}$.\n*   Moves to vertex $0$. This action is chosen with probability $\\frac{1}{2}$.\n*   Moves to vertex $1$. This action is chosen with probability $\\frac{1}{2}$.\n*   Moves to vertex $3$ and paints it. This action is chosen with probability $\\frac{1}{2}$.\n*   Moves to vertex $1$. This action is chosen with probability $1$.\n*   Moves to vertex $0$. This action is chosen with probability $\\frac{1}{2}$.\n*   Moves to vertex $2$ and paints it. This action is chosen with probability $\\frac{1}{2}$.\n*   Moves to vertex $4$ and paints it. This action is chosen with probability $\\frac{1}{2}$.\n\nHe behaves in this way with probability $\\frac{1}{128}$, in which case the number of operations is $8$. The expected number of operations is $20$."],["123456 185185","69292914"]],"created_at":"2026-03-03 11:01:13"}}