Good Bye 2017 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

math

probabilities

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. New Year and Arbitrary Arrangement

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given three integers *k*, *p*_{a} and *p*_{b}.

You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability *p*_{a} / (*p*_{a} + *p*_{b}), add 'a' to the end of the sequence. Otherwise (with probability *p*_{b} / (*p*_{a} + *p*_{b})), add 'b' to the end of the sequence.

You stop once there are at least *k* subsequences that form 'ab'. Determine the expected number of times 'ab' is a subsequence in the resulting sequence. It can be shown that this can be represented by *P* / *Q*, where *P* and *Q* are coprime integers, and . Print the value of .

Input

The first line will contain three integers integer *k*, *p*_{a}, *p*_{b} (1 ≤ *k* ≤ 1 000, 1 ≤ *p*_{a}, *p*_{b} ≤ 1 000 000).

Output

Print a single integer, the answer to the problem.

Examples

Input

1 1 1

Output

2

Input

3 1 4

Output

370000006

Note

The first sample, we will keep appending to our sequence until we get the subsequence 'ab' at least once. For instance, we get the sequence 'ab' with probability 1/4, 'bbab' with probability 1/16, and 'aab' with probability 1/8. Note, it's impossible for us to end with a sequence like 'aabab', since we would have stopped our algorithm once we had the prefix 'aab'.

The expected amount of times that 'ab' will occur across all valid sequences is 2.

For the second sample, the answer is equal to .

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 22:09:23 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|