Unfair Sugoroku

AtCoder

IDabc298_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

4 2 3 3 2

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}$.

Input #2

6 4 2 1 1

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.

Input #3

100 1 1 10 10

Output #3

264077814

API Response (JSON)

{
  "problem": {
    "name": "Unfair Sugoroku",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc298_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi and Aoki will play a game of sugoroku.  \nTakahashi starts at point $A$, and Aoki starts at point $B$. They will take turns throwing dice.  \nTakahashi's die shows $1, 2, \\ldots, P$ with equal...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments