题目描述
有一场足球比赛，还有 $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
input
1
1 2
1 2output
250000002
比赛还剩 $1$ 秒，主队获胜当且仅当主队进球且客队不进球，概率为 $\frac{1}{2} \times (1 - \frac{1}{2}) = \frac{1}{4}$， $4$ 关于 $10^9+7$ 的逆元为 $250 000 002$。
样例 2
input
10
1 1
1 3output
762519270
获胜概率为 $1 - \left(\frac{1}{3}\right)^{10}$。
样例 3
input
233333
233 2333333
566 5666666output
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 | $ \leq 10^5$ | |
| 18 | $ \leq 2\times 10^5$ | $p = 1$ |
| 19 | $ \leq 5\times 10^5$ | |
| 20 | $ \leq 10^6$ | $q = 0$ |
| 21 | $ \leq 10^6$ | |
| 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$。注意常数优化！注意内存限制！