9328: ABC298 —— E - Unfair Sugoroku
[Creator : ]
Description
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$.
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$.
Input
The input is given from Standard Input in the following format:
```
$N$ $A$ $B$ $P$ $Q$
```
```
$N$ $A$ $B$ $P$ $Q$
```
Output
Print the answer.
Constraints
$2 \leq N \leq 100$
$1 \leq A, B < N$
$1 \leq P, Q \leq 10$
All values in the input are integers.
$1 \leq A, B < N$
$1 \leq P, Q \leq 10$
All values in the input are integers.
Sample 1 Input
4 2 3 3 2
Sample 1 Output
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}$.
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 2 Input
6 4 2 1 1
Sample 2 Output
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.
Here, Takahashi goes to point 5, Aoki goes to point 3, and Takahashi goes to point 6, so Takahashi always wins.
Sample 3 Input
100 1 1 10 10
Sample 3 Output
264077814