#6513. 「雅礼集训 2018 Day10」足球大战

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一场足球比赛,还有 n 秒就要结束了,比分还是 0:0

主队每秒进球概率为 p ,客队每秒进球概率为 q ,求主队获胜概率。

注意,一秒钟一个队最多进一个球,主队获胜当且仅当主队进球比客队多。

为了避免精度误差,把最后的答案化成最简分数 \frac{x}{y} ,输出 x y 关于 (10^9+7) 的逆元的乘积即可。

根据费马小定理, \frac{x}{y} \bmod (10^9+7) = x\times y^{10^9+5} \bmod (10^9+7) .

p q 将通过一种特别的方式给出:给出 pa, pb, qa, qb p = \frac{pa}{pb}, q = \frac{qa}{qb}

输入格式

第一行一个正整数 n ,表示剩余的秒数。

第二行两个整数 pa, pb, p = \frac{pa}{pb} ,表示主队每秒进球期望数。

第三行两个整数 qa, qb, q = \frac{qa}{qb} ,表示客队每秒进球期望数。

输出格式

输出一行一个整数,表示把答案化成最简分数 \frac{x}{y} 后, x 乘以 y 的逆元关于 (10^9+7) 取模后的值。

样例

样例输入 1

1
1 2
1 2

样例输出 1

250000002

样例解释 1

比赛还剩 1 秒,主队获胜当且仅当主队进球且客队不进球,概率为 \frac{1}{2} \times (1 - \frac{1}{2}) = \frac{1}{4} 4 关于 10^9+7 的逆元为 250 000 002

样例输入 2

10
1 1
1 3

样例输出 2

762519270

样例解释 2

获胜概率为 1 - \left(\frac{1}{3}\right)^{10}

样例输入 3

233333
233 2333333
566 5666666

样例输出 3

46387011

数据范围与提示

测试点编号 n 特殊情况
1 =1
2 \leq 2
3 \leq 5
4 \leq 10
5 \leq 20
6 \leq 50 p = 0
7 \leq 100
8 \leq 200 q = 1
9 \leq 500
10 \leq 1000 p = q = \frac{1}{2}
11 \leq 2000
12 \leq 5000 q = 0
13 \leq 10^4
14 \leq 2\times 10^4 p = q
15 \leq 5\times 10^4
16 \leq 10^5 p = 1
17
18 \leq 2\times 10^5 p = 1
19 \leq 5\times 10^5
20 \leq 10^6 q = 0
21
22 \leq 2\times 10^6 p = q
23 \leq 5\times 10^6
24 p = q
25

对于所有的数据, 1 \leq n \leq 10^7, 0 \leq pa,qa \leq 10^9, 1 \leq pb, qb \leq 10^9, pa \leq pb, qa \leq qb 。注意常数优化!注意内存限制!