시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 512 MB 209 62 43 46.237%

문제

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

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로 나눈 나머지를 공백을 사이에 두고 차례대로 출력한다.

예제 입력 1

2
10 21
18 25

예제 출력 1

11 75

첫째 날에 메시의 기분이 좋을 확률은 11/21이고, 둘째 날은 7/25이다. 메시가 이틀 모두 기분이 좋을 확률은 두 확률의 곱인 11/75이다.

예제 입력 2

5
1 2
1 3
1 4
1 5
1 6

예제 출력 2

1 6

예제 입력 3

8
2 39
1 6
23 24
7 37
31 45
23 37
37 48
8 11

예제 출력 3

245 1246752

예제 입력 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

예제 출력 4

419783776 306004046