Score : $500$ points

问题陈述

高桥和青木将进行一场 sugoroku 游戏。
高桥从点 $A$ 开始，青木从点 $B$ 开始。他们轮流投掷骰子。
高桥的骰子显示数字 $1, 2, \ldots, P$ 的概率相等，而青木的骰子显示数字 $1, 2, \ldots, Q$ 的概率也相等。
当位于点 $x$ 的玩家投掷骰子且显示数字 $i$ 时，他将移动到点 $\min(x + i, N)$。
第一个到达点 $N$ 的玩家赢得游戏。
求在高桥先行的情况下，他赢得游戏的概率对 $998244353$ 取模的结果。

如何计算模 $998244353$ 下的概率 可以证明所求概率总是有理数。此外，本问题的约束条件保证了，如果该概率表示为不可约分数 $\frac{y}{x}$，则 $x$ 不会被 $998244353$ 整除。
这里存在一个唯一的整数 $z$，满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod {998244353}$。请报告这个 $z$ 值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point $A$, and Aoki starts at point $B$. They will take turns throwing dice.
Takahashi's die shows $1, 2, \ldots, P$ with equal probability, and Aoki's shows $1, 2, \ldots, Q$ with equal probability.
When a player at point $x$ throws his die and it shows $i$, he goes to point $\min(x + i, N)$.
The first player to reach point $N$ wins the game.
Find the probability that Takahashi wins if he goes first, modulo $998244353$.

How to find a probability modulo $998244353$ It can be proved that the sought probability is always rational. Additionally, the constraints of this problem guarantee that, if that probability is represented as an irreducible fraction $\frac{y}{x}$, then $x$ is indivisible by $998244353$.
Here, there is a unique integer $z$ between $0$ and $998244352$ such that $xz \equiv y \pmod {998244353}$. Report this $z$.

Constraints

• $2 \leq N \leq 100$
• $1 \leq A, B < N$
• $1 \leq P, Q \leq 10$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $A$ $B$ $P$ $Q$

Output

Print the answer.

Sample Input 1

4 2 3 3 2

Sample Output 1

665496236

If Takahashi's die shows $2$ or $3$ in his first turn, he goes to point $4$ and wins.
If Takahashi's die shows $1$ in his first turn, he goes to point $3$, and Aoki will always go to point $4$ in the next turn and win.
Thus, Takahashi wins with the probability $\frac{2}{3}$.

Sample Input 2

6 4 2 1 1

Sample Output 2

1

The dice always show $1$.
Here, Takahashi goes to point $5$, Aoki goes to point $3$, and Takahashi goes to point $6$, so Takahashi always wins.

Sample Input 3

100 1 1 10 10

Sample Output 3

264077814

update @ 2024/3/10 12:22:34