J. 重生之我在崩铁强化获得满分遗器

    Type: Default 1000ms 256MiB

重生之我在崩铁强化获得满分遗器

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

第 14 th 南工程校赛L题也是和期望有关的题,

十分容易,

所以这道题也十分容易。

$\text{Brolysia}$ 得到了一件初始属性十分不错的遗器,想要对其进行强化。

遗器初始为 $0$ 级,目标等级为 $n$。

在等级 $i$($0 \le i \le n-1$)时,每次强化尝试:

  • 有 pip_i 的概率成功,升至 i+1i+1 级;

  • 有 1−pi1-p_i 的概率失败,碎回 00 级。

概率 $p_i = \frac{a_i}{b_i}$。每次强化相互独立。

求从 $0$ 级强化到 $n$ 级所需尝试次数的期望值,答案对 $10^9+7$ 取模。

Input Format

第一行一个整数 $n$。

接下来 $n$ 行,每行两个整数 $a_i, b_i$,表示 $p_i = \frac{a_i}{b_i}$。

保证 $1 \le n \le 10^6$,$1 \le a_i < b_i \le 10^9$。

Output Format

一行一个整数,表示期望尝试次数模 $10^9+7$ 的结果。

1
1 2
2
2
1 2
1 3
9
3
1 2
2 3
1 4
22

Hint

对于第一组样例,遗器只需要被强化到一级,成功概率为 $\frac{1}{5}$,期望次数为 $\frac{1}{p_0} = 5$。