/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋君と青木君がすごろくをします。
高橋君ははじめ地点 A、青木君ははじめ地点 B にいて、交互にサイコロを振ります。
高橋君が振るサイコロは 1, 2, \ldots, P の出目が一様ランダムに出るサイコロで、青木君が振るサイコロは 1, 2, \ldots, Q の出目が一様ランダムに出るサイコロです。
地点 x にいるときに自分の振ったサイコロの出目が i であるとき、地点 \min(x + i, N) に進みます。
地点 N に先に着いた人をすごろくの勝者とします。
高橋君が先にサイコロを振るとき、高橋君が勝つ確率を \text{mod }998244353 で求めてください。
確率 \text{mod }998244353 とは
この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod {998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- 2 \leq N \leq 100
- 1 \leq A, B < N
- 1 \leq P, Q \leq 10
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A B P Q
出力
答えを出力せよ。
入力例 1
4 2 3 3 2
出力例 1
665496236
高橋君が最初の手番で 2 あるいは 3 の出目を出すと、高橋君は地点 4 に進んで高橋君が勝利します。
高橋君が最初の手番で 1 の出目を出すと、高橋君は地点 3 に進み、青木君は次の手番で必ず地点 4 に進んで青木君が勝利します。
よって、高橋君が勝つ確率は \frac{2}{3} です。
入力例 2
6 4 2 1 1
出力例 2
1
サイコロの出目は常に 1 です。
このとき高橋君が地点 5 に進み、次いで青木君が地点 3 に進み、次いで高橋君が地点 6 に進むので、高橋君は必ず勝ちます。
入力例 3
100 1 1 10 10
出力例 3
264077814
Score : 500 points
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