You 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 $Q \neq 0 \operatorname{mod}(10^{9} + 7)$. Print the value of $P \cdot Q^{-1} \operatorname{mod}(10^{9} + 7)$.


-----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 $\frac{341}{100}$.

Difficulty: HARD
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
mod = 1000000007
N = 1005
(k, pa, pb) = list(map(int, input().split()))
dp = [[0 for x in range(N)] for y in range(N)]

def fast_expo(a, b):
	ret = 1
	while b:
		if b % 2 == 1:
			ret = ret * a % mod
		b //= 2
		a = a * a % mod
	return ret

def inv(x):
	return fast_expo(x, mod - 2) % mod

def dp_val(a, b):
	if b >= k:
		return b
	return dp[a][b]
for i in range(k):
	dp[k][i] = (i + k + pa * inv(pb)) % mod
den = inv(pa + pb)
for i in range(k - 1, 0, -1):
	for j in range(k - 1, -1, -1):
		dp[i][j] = pa * dp_val(i + 1, j) * den % mod + pb * dp_val(i, i + j) * den % mod
		dp[i][j] %= mod
print(dp[1][0])


(k, pa, pb) = list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = (pa + pb) * pow(pb, MOD - 2, MOD) % MOD
rAB = pow(pa + pb, MOD - 2, MOD)
rB = pow(pb, MOD - 2, MOD)
memo = {}

def dfs(a, ab):
	if ab >= k:
		return ab
	if a + ab >= k:
		return (a + MOD - 1 + (pa + pb) * rB + ab) % MOD
		return a - 1 + (pa + pb) / pb + ab
	if (a, ab) in memo:
		return memo[a, ab]
	res = dfs(a + 1, ab) * pa * rAB + dfs(a, ab + a) * pb * rAB
	memo[a, ab] = res = res % MOD
	return res
print(dfs(1, 0))


import sys
input = sys.stdin.readline
dp = {}
mod = int(1000000007)
sys.setrecursionlimit(100000)

def bigmod(n, p):
	p = int(p)
	if p == 0:
		return 1
	x = bigmod(n, p / 2)
	x = x * x % mod
	if p % 2 == 1:
		x = x * n % mod
	return x
(k, pa, pb) = map(int, input().split())
r = bigmod(pa + pb, mod - 2)
r1 = bigmod(pb, mod - 2)
r1 = pa * r1 % mod
p = pa * r % mod
q = pb * r % mod

def cal(k1, a1):
	if k1 + a1 >= k:
		return (k1 + a1 + r1) % mod
	if (k1, a1) in dp:
		return dp[k1, a1]
	dp[k1, a1] = (cal(k1 + a1, a1) * q % mod + cal(k1, a1 + 1) * p % mod) % mod
	return dp[k1, a1]
print(cal(0, 1))


from collections import defaultdict as di
import sys
sys.setreqursiondepth = 1000000
MOD = int(1000000000.0 + 7)

def modinvEuler(x, mod):
	return pow(x, mod - 2, mod)
(k, pa, pb) = [int(x) for x in input().split()]
Pa = pa * modinvEuler(pa + pb, MOD) % MOD
Pb = (1 - Pa) % MOD
Ea = modinvEuler(Pa, MOD)
Eb = modinvEuler(Pb, MOD)
Pbinv = modinvEuler(Pb, MOD)
mem = di()

def f(na, ns):
	if ns >= k:
		return ns
	if na + ns >= k:
		total = ns
		total += na
		total += Pa * Pbinv
		total %= MOD
		return total
	if (na, ns) not in mem:
		mem[na, ns] = (Pa * f(na + 1, ns) + Pb * f(na, ns + na)) % MOD
	return mem[na, ns]
print(f(1, 0) % MOD)


(k, a, b) = map(int, input().split())
m = 1000000007
d = a * pow(b, m - 2, m) % m
c = pow(a + b, m - 2, m)
(u, v) = ([0] * k, [0] * k)
for s in range(k, 0, -1):
	v[s - 1] = s + d
	for i in range(s, k):
		j = max(i - s, s - 1)
		v[i] = c * (a * u[i] + b * (s + v[j])) % m
	(u, v) = (v, u)
print(u[k - 1])


m = 10 ** 9 + 7

def rainy(K, PA, PB):
	P = PA * pow(PB, m - 2, m) % m
	Q = pow(PA + PB, m - 2, m)
	(FINAL, CURR) = ([0] * K, [0] * K)
	for s in range(K, 0, -1):
		CURR[s - 1] = s + P
		for i in range(s, K):
			j = max(i - s, s - 1)
			CURR[i] = Q * (PA * FINAL[i] + PB * (s + CURR[j])) % m
		(FINAL, CURR) = (CURR, FINAL)
	return FINAL[K - 1]
(k, a, b) = map(int, input().split())
print(rainy(k, a, b))


import math
import sys
(k, pa, pb) = list(map(int, input().split()))
memo = {}
sys.setrecursionlimit(1500 * 1500 * 2)
MOD = 10 ** 9 + 7

def pow(a, b):
	ret = 1
	while b > 0:
		if b & 1:
			ret = ret * a % MOD
		a = a * a % MOD
		b //= 2
	return ret

def inv(a):
	return pow(a, MOD - 2)
Pa = pa * inv(pa + pb)
Pb = pb * inv(pa + pb)
pa_inv_pb = pa * inv(pb)

def f(total_a, total_ab):
	if total_a + total_ab >= k:
		return total_a + total_ab + pa_inv_pb
	if (total_a, total_ab) in memo:
		return memo[total_a, total_ab]
	Best = 0
	Best += Pa * f(total_a + 1, total_ab)
	Best %= MOD
	Best += Pb * f(total_a, total_a + total_ab)
	Best %= MOD
	memo[total_a, total_ab] = Best
	return Best
print(f(1, 0) % MOD)