New Year and Arbitrary Arrangement
Contest: Good Bye 2017
Difficulty rating: 2200
Tags: dp, math, probabilities

You are given three integers k, pa and pb.

You will construct a sequence with the following algorithm: Initially, start with the empty sequence. Each second, you do the following. With probability pa / (pa + pb), add 'a' to the end of the sequence. Otherwise (with probability pb / (pa + pb)), 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 $$Q \neq 0 \bmod (10^9 + 7)$$. Print the value of $$P \cdot Q^{-1} \bmod (10^9 + 7)$$.

Input format:
The first line will contain three integers integer k, pa, pb (1 ≤ k ≤ 1 000, 1 ≤ pa, pb ≤ 1 000 000).

Output format:
Print a single integer, the answer to the problem.

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

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 $${ \frac { 3 4 1 } { 1 0 0 } }$$.

Example input:
1 1 1

Example output:
2

Example input:
3 1 4

Example output:
370000006

Editorial:
The main trickiness of this problem is that the sequence could potentially get arbitrary long, but we want an exact answer. In particular, it helps to think about how to reduce this problem to figuring out what state we need to maintain from a prefix of the sequence we've built in order to simulate our algorithm correctly. This suggests a dynamic programming approach.
For our dp state, we need to keep track of something in our prefix. First, the most obvious candidate is we need to keep track of the number of times 'ab' occurs in the prefix (this is so we know when to stop). However, using only this is not enough, as we can't distinguish between the sequences 'ab' and 'abaaaa'. So, this suggests we also need to keep track of the number of 'a's.
Let dp[i][j] be the expected answer given that there are i subsequences of the form 'a' in the prefix and j subsequences of the form 'ab' in the prefix.
Then, we have something like dp[i][j] = (pa * dp[i + 1][j] + pb * dp[i][i + j]) / (pa + pb). The first term in this sum comes from adding another 'a' to our sequence, and the second comes from adding a 'b' to our sequence. We also have dp[i][j] = j if j ≥ k as a base case. The answer should be dp[0][0].
However, if we run this as is, we'll notice there are still some issues. One is that i can get arbitrarily large here, as we can keep adding 'a's indefinitely. Instead, we can modify our base case to when i + j ≥ k. In this case, the next time we get a 'b', we will stop, so we can find a closed form for this scenario. The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored. To fix this, we can adjust our answer to be dp[1][0].