====== Σ ======

===== 풀이 =====
  * 문제 지문이, 문제라기보다는 강의에 가깝다. 내용을 이해하고서 시키는 대로 짜면 된다.
  * 다만 문제에서 설명하는 방법은, 분수를 모듈러역원을 이용해서 정수로 표현하고 나면, 분수의 합을 그냥 정수의 합으로 편리하게 계산할 수 있다는 것인데, 이렇게 시키는대로 짜면 조금 느리다. 모듈러 역원을 구하는 데에 O(logn)이 들기 때문에, m개의 분수를 모두 정수 표현으로 바꾸려면 O(mlogn)이 걸린다.
  * 그럼 대신 그냥 분수 상태에서 통분을 시켜서 더하는 방법을 사용해보자. 문제에서는 이렇게 하면 분자와 분모의 값이 너무 커지기 때문에 안된다고 설명하고 있지만, 어차피 결과값을 최종적으로 모듈러 역원을 이용한 정수 표현으로 바꿔서 출력하는 것이 목표라면, 매 계산마다 분자와 분모에 모듈러를 취해도 정수 표현 변환값은 동일하게 유지된다. 이렇게 하면, 통분해서 분수를 더하는 것은 한번에 O(1), 전체에는 O(m)이고, 마지막에만 모듈러 역원을 한번 구하면 되므로 총 시간복잡도는 O(m+logn)이 된다. 여기서 n에 해당하는 값은, 최종 계산된 분수에서의 분모값이고, 그 분모는 P(=1,000,000,007)로 나눈 나머지를 취한 값이므로 최대 P가 된다. O(m+logP)라고 쓸수도 있지만, P가 상수이므로 그냥 전체 복잡도를 O(m)이라고 써도 무방.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13172. Σ".

- Problem link: https://www.acmicpc.net/problem/13172
- Solution link: http://www.teferi.net/ps/problems/boj/13172
"""

import sys
 
MOD = 1_000_000_007


def main():
    M = int(sys.stdin.readline())
    numer, denom = 0, 1
    for _ in range(M):
        N, S = [int(x) for x in sys.stdin.readline().split()]
        numer, denom = (numer * N + denom * S) % MOD, (denom * N) % MOD
    print(numer * pow(denom, -1, MOD) % MOD)        


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}