Ability

Time limit2sMemory limit512 MB

Summary

Compute the expected damage of one attack where abilities are tried in a uniformly random order without replacement until one fires, and output the fraction modulo 1e9+7.

Level: Medium7 of 10
Topics: Probability, Math, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

A player fights monsters in a web game and has all $N$ attack abilities equipped at once. The abilities are numbered 1 through $N$ .

Ability $i$ has a trigger probability $p_i$ and a damage value $d_i$ . When the player issues a trigger command to ability $i$ , the ability fires with probability $p_i$ and deals $d_i$ damage to the opponent, and with probability $1 - p_i$ it does not fire and nothing happens.

One attack opportunity runs like this.

Choose one of the equipped abilities. Every ability is equally likely to be chosen.
Issue a trigger command to the chosen ability.
If the ability fires, the attack opportunity is spent and the process ends.
If it does not fire, choose one of the abilities that has not received a command yet, again with equal probability, then go back to step 2.
If every ability has received a command and none of them fired, the attack opportunity is spent with no damage.

Given the trigger probability and the damage of all $N$ abilities, compute the expected damage dealt in one attack opportunity.

Input

The first line contains the number of abilities $N$ ( $1 \le N \le 5000$ ).

Line $i$ of the next $N$ lines contains two integers $p_i$ and $d_i$ ( $1 \le p_i, d_i \le 10^9$ ) separated by a space. Ability $i$ fires with probability $p_i / 10^9$ and deals $d_i$ damage when it fires.

Output

Print the expected damage dealt in one attack opportunity. Write the expected value as an irreducible fraction $a/b$ and print $(a \times b^{-1}) \bmod (10^9 + 7)$ instead, where $b^{-1}$ is the multiplicative inverse of $b$ modulo $10^9 + 7$ . This value exists for every input given in this problem.

Examples8

Example 1
Input
```
1
500000000 10
```
Expected output
```
5
```

Example 2

Input

Expected output

93531355

Example 3
Input
```
1
1000000000 1000000000
```
Expected output
```
1000000000
```
Example 4
Input
```
1
1 1
```
Expected output
```
857142863
```

Example 5

Input

3
1000000000 1
1000000000 2
1000000000 3

Expected output

Example 6
Input
```
2
1 1000000000
1000000000 1
```
Expected output
```
571428577
```
Example 7
Input
```
5
2 3
4 5
6 7
8 9
10 11
```
Expected output
```
55532270
```

Example 8

Input

6
999999999 1000000000
1000000000 999999999
500000000 2
1 1
123456789 987654321
999999998 3

Expected output

326678928