Messi An-Gimossi

시간 제한2.5초메모리 제한512 MB

요약
각 날 기분이 나쁠 확률이 A_i/B_i로 주어질 때, N일 내내 기분이 좋을 확률을 기약분수로 구해 분자와 분모를 10^9+7로 나눈 나머지를 출력한다.
난이도

보통10점 중 5점

유형
수학, 정수론, 조합론, 구현
정답자
아직 제출이 없습니다

문제

메시는 축구 선수이다. 메시는 기분이 안 좋다.

messi: Messi An-Gimossi

메시의 기분은 예측 가능하다. N일의 기분 예보가 있다. 기분이 나쁠 확률이 각 날마다 기약분수 A/B 꼴로 주어진다.

기분이 나쁜 것이 독립적인 사건이라 할 때, 메시의 기분이 매일 좋을 확률(N일 내내 좋을 확률)을 기약분수로 구해 보자.

입력

첫째 줄에 예보의 수 N이 주어진다. (1 ≤ N ≤ 105)

둘째 줄부터 N개의 줄에 걸쳐, Ai와 Bi가 주어진다. 이는 i번째 날에 기분이 나쁠 확률이 Ai/Bi라는 뜻이다. (1 ≤ Ai < Bi ≤ 107, Ai와 Bi는 서로소인 정수)

출력

메시의 기분이 N일 내내 좋을 확률이 기약분수 A/B와 같다고 할 때, A를 109+7로 나눈 나머지와 B를 109+7로 나눈 나머지를 공백을 사이에 두고 차례대로 출력한다.

예제4

  1. 예제 1

    입력
    2
10 21
18 25
    예상 출력
    11 75

  2. 예제 2

    입력
    5
1 2
1 3
1 4
1 5
1 6
    예상 출력
    1 6

  3. 예제 3

    입력
    8
2 39
1 6
23 24
7 37
31 45
23 37
37 48
8 11
    예상 출력
    245 1246752

  4. 예제 4

    입력
    12
13 67
7 78
59 167
127 153
116 147
133 187
112 115
33 61
47 83
63 94
164 167
83 161
    예상 출력
    419783776 306004046