능력 Batch Compilation commands

그는 요즘 여러 능력을 가지고 몬스터들과 싸우는 웹게임을 열심히 하고 있다. 그는 지금 $N$개의 공격 능력을 가지고 있고 이 모든 능력을 장착하고 있다. 그는 능력들을 편하게 관리하고자 각 능력에 1 이상 $N$ 이하의 자연수 번호를 붙였다.

$i$번 능력에는 그 능력이 발동될 확률 $p_{i}$와 상대에게 입히는 피해량 $d_{i}$가 책정되어 있다. 따라서 그가 $i$번 능력에 발동 명령을 내리면, $p_{i}$의 확률로 능력이 발동되어 상대에게 $d_{i}$만큼의 피해를 입히고, $(1 - p_{i})$의 확률로 능력이 발동되지 않아 아무 일도 일어나지 않는다. 그가 어떤 능력(들)을 장착한 채로 상대방을 공격할 기회를 얻었다면, 아래 과정이 일어난다:

• 가지고 있는 모든 능력들 중 하나를 임의로 고른다. 모든 능력을 고를 확률은 서로 같다. 고른 능력에 발동 명령을 내린다. 만약 이 능력이 발동되었다면, 공격 기회를 잃고 과정이 끝난다. 하지만 이 능력이 발동되지 않았다면, 아직 발동 명령을 내려 보지 않은 능력들 중 하나를 동일한 확률로 고른 후, 다시 발동 명령을 내린다. 만약 능력이 발동되었다면 공격 기회를 잃은 후 과정을 끝내고, 발동되지 않았다면 같은 과정을 더 이상 발동 명령을 내려 보지 않은 능력이 없을 때까지 반복한다. 모든 능력에 발동 명령을 내렸음에도 발동된 능력이 하나도 없으면 공격 기회를 잃는다.

현재 그가 장착하고 있는 $N$개의 능력이 발동될 확률과 상대에게 입히는 피해량이 주어질 때, 한 번의 공격 기회에서 주게 되는 피해량의 기댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 능력의 수를 나타내는 자연수 $N$이 주어진다.

다음 $N$개의 줄에는 능력들의 정보가 주어진다. 이 중 $i$ ($1 \le i \le N$)번째 줄에는 $i$번 능력이 발동될 확률과 상대에게 입히는 피해량을 의미하는 두 정수 $p_{i}$, $d_{i}$ ($1 \le p_{i}, d_{i} \le 10^{9}$)이 공백을 사이로 두고 주어진다. 이는 $i$번 능력은 $ p_{i} / 10^{9}$의 확률로 발동하는 능력이며 상대에게 $d_{i}$만큼의 피해를 입힌다는 의미이다.

부분문제

부분문제	점수	N
1	10	1 ≤ N ≤ 200
2	90	1 ≤ N ≤ 5,000

출력

그가 한 번의 공격 기회에서 주게 되는 피해량의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 가 된다면, 을 대신 출력하도록 한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

입출력 예제

예제 1

입력

1
500000000 10

출력

5

예제 2

입력

9
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
9 1

출력

93531355