908D. New Year and Arbitrary Arrangement[概率期望dp]

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 $\frac {pa}{ (pa + pb)}, $add ‘a’ to the end of the sequence. Otherwise (with probability $\frac {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 \pmod {10^9+7}$. Print the value of $P·Q^{-1} \pmod {10^9+7}$ .

Input

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

Output

Print a single integer, the answer to the problem.

Examples

input

1
1 1 1

output

1
2

input

1
3 1 4

output

1
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}​$

Solution

$dp_{i,j}$ 表示前缀有 $i$ 个a,$j$ 个ab时候的期望,考虑往后添a和b两种情况。

$$
dp(i,j)=\frac{pa}{pa+pb}dp(i+1,j)+\frac {pb}{pa+pb}dp(i,j+i)
$$

边界:$i+j ≥ k$ (只要往后加一个b就能结束)

设$A=\frac{pa}{pa+pb}$,$B=\frac{pb}{pa+pb}$
$i+j ≥ k$ 时

$$
dp[i][j]=B(i+j)+AB(i+j+1)+A^2B(i+j+2)+A^3B(i+j+3)……
$$

最后推出来是$i+j+\frac{pa}{pb}$
答案:因为前面加多少个b都没用,所以答案就是$dp_{1,0}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const ll mod=1e9+7;
ll ksm(ll x,int y)
{
ll sum=1;
x%=mod;

while (y)
{
if (y&1) sum=sum*x%mod;
y>>=1;
x=x*x%mod;
}
return sum;
}
ll dp[1010][1010],k,pa,pb,inva,invb,invab;
int main()
{
k=read();pa=read();pb=read();
inva=ksm(pa,(int)mod-2);invb=ksm(pb,(int)mod-2);invab=ksm(pa+pb,(int)mod-2);
for (ll i=k;i>=1;i--)
for (ll j=k;j>=0;j--)
{
if (i+j>=k) dp[i][j]=(i+j+pa*invb%mod)%mod; else
dp[i][j]=(dp[i+1][j]*pa%mod*invab%mod+dp[i][j+i]*pb%mod*invab%mod)%mod;
}
printf("%I64d",dp[1][0]%mod);
return 0;
}