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

有一场足球比赛，还有 $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)$ 取模后的值。

| 测试点编号 | $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$。注意常数优化！注意内存限制！