능력 Batch 컴파일 명령

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

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

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

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

입력

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

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

부분문제

출력

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

입출력 예제