Strongly Connected Tournament
Contest: Hello 2018
Difficulty rating: 2800
Tags: dp, graphs, math, probabilities

There is a chess tournament in All-Right-City. n players were invited to take part in the competition. The tournament is held by the following rules:

1. Initially, each player plays one game with every other player. There are no ties;
2. After that, the organizers build a complete directed graph with players as vertices. For every pair of players there is exactly one directed edge between them: the winner of their game is the startpoint of this edge and the loser is the endpoint;
3. After that, the organizers build a condensation of this graph. The condensation of this graph is an acyclic complete graph, therefore it has the only Hamiltonian path which consists of strongly connected components of initial graph A1 → A2 → ... → Ak.
4. The players from the first component A1 are placed on the first $$|A_{1}|$$ places, the players from the component A2 are placed on the next $$|A_{2}|$$ places, and so on.
5. To determine exact place of each player in a strongly connected component, all the procedures from 1 to 5 are repeated recursively inside each component, i.e. for every i = 1, 2, ..., k players from the component Ai play games with each other again, and so on;
6. If a component consists of a single player, then he has no more rivals, his place is already determined and the process stops.

The players are enumerated with integers from 1 to n. The enumeration was made using results of a previous tournament. It is known that player i wins player j (i < j) with probability p.

You need to help to organize the tournament. Find the expected value of total number of games played by all the players.

It can be shown that the answer can be represented as $$\frac{p}{q}$$, where P and Q are coprime integers and $$Q \not\equiv 0 \pmod{998244353}$$. Print the value of P·Q - 1 modulo 998244353.

If you are not familiar with any of the terms above, you can read about them here.

Input format:
The first line of input contains a single integer n (2 ≤ n ≤ 2000) — the number of players.

The second line contains two integers a and b (1 ≤ a < b ≤ 100) — the numerator and the denominator of fraction $$\frac{a}{b} = p$$.

Output format:
In the only line print the expected value of total number of games played by all the players. Print the answer using the format above.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the expected value is 4.

In the second example the expected value is $$\frac{27}{7}$$.

In the third example the expected value is $${ \frac { 5 6 } { 5 } }$$.

Example input:
3
1 2

Example output:
4

Example input:
3
4 6

Example output:
142606340

Editorial:
Probability of player i to win player j depends on whether i < j only, so the answer for subset of players of size s doesn't depend on the set, only on its size. Let ans(s) be the answer for set of s players.
Lets calculate the answer using dynamic programming. ans(0) = ans(1) = 0. For larger s lets use law of total expected value. Let i be size of the last strongly connected component.
$${ \mathrm { a n s } } ( s ) = \sum _ { i = 1 } ^ { s } { \mathrm { s t r o n g } } ( i ) \cdot c p ( s, i ) \cdot ( i \cdot ( s - i ) + { \frac { i \cdot ( i - 1 ) } { 2 } } + { \mathrm { a n s } } ( i ) + { \mathrm { a n s } } ( s - i ) )$$ — equation (1).
i-th term consists of three factors. The first factor strong(i) is the probability of graph of i players be strong connected. We'll describe how to calculate it below. The second factor cp(s, i) is the probability of existing i players in set of s players such that these i players lost all the rest players. The product of these two factors is the probability that size of the last strongly connected component is i.
The third factor is expected value of number of games with the condition of the last component has size i. i·(s - i) is number of games between players of the last component and the rest players. $$\frac{i \cdot (i-1)}{2}$$ is number of games inside of the last component. ans(i) is the expected value of number of games in the last component on the next round. After that we need to add number of games between all the players except for the last component and the value of ans for sizes of other components. Note that this terms describe the game on set of players except the last component. Therefore the sum of these terms is ans(s - i).
Also note that the right part of equation (1) contains term that uses ans(s). So ans(s) is using ans(s) for calculating itself. To overcome this lets move this term to the left side and solve linear equation with variable ans(s).
How to calculate strong(s)? strong(1) = 1 because the graph with one vertice is strong connected. When s ≥ 2 we have $${ \mathrm { s t r o n g } } ( s ) = 1 - \sum _ { i = 1 } ^ { s - 1 } { \mathrm { s t r o n g } } ( i ) \cdot c p ( s, i )$$. Here we use law of total probability and calculate the answer by iterating i over possible values of size of the last component.
How to calculate cp(s, i)? cp(s, 0) = 1 because there are 0 players who lost games to the others. cp(s, i) = cp(s - 1, i)·(1 - p)i + cp(s - 1, i - 1)·ps - i where p is the probability of winning the player with less index. Here we use law of total probability again. The first term describe the case when player with the largest index is not in the set of players that lost to the others, so he should win all the players from the set. The second term describes the case when player with the largest index is in the set. In this case he should lose the game to all the players who is not in the set.
In summary, value of ans(n) can be calculated in time $${\mathcal {O}}(n^{2})$$ and this value is the answer for the problem.