주어진 기약분수의 합을 1000000007로 나눈 나머지 집합 위로 사영시키는 문제입니다. 이 때의 규칙은 주어진 기약분수 $\frac{a}{b}$에 대하여 $a\times b^{-1}\equiv k\mod r$을 만족할 때 k를 모듈러 위에서 분수를 대신하는 값으로 합니다. 또한 기약분수의 합 $\frac{a}{b}+\frac{c}{d}$는 $a\times b^{-1}\equiv k\mod r$이고 $c\times d^{-1}\equiv l\mod r$이면 $k+l$이 됩니다. 이 경우 주어진 분수들에 대하여 분수의 합을 1000000007로 나눈 나머지 집합 위로 사영시킨 값을 찾는 문제인데, 기약분수라는 말을 사실 신경쓸 필요가 없습니다. 먼저 페르마의 소정리에 의해 $a^p\equiv a\mod p$입니다. 이제 여기에 a-2를 양변에 곱하면 $a^{p-2}\equiv a^{-1}\mod p$이므로 p에 대한 a의 곱셈의 역원은 ap-2입니다. 따라서 주어진 기약분수 $\frac{a}{b}$에 대해서 $a\times b^{-1}\equiv a\times b^{r-2}$를 만족합니다. 이제 적당한 정수 m에 대하여 분수 $\frac{am}{bm}$가 있다고 했을 때 같은 방법으로 구해보면 아래와 같이 됩니다.
\[\frac{am}{bm}=am\times (bm)^{-1}\equiv am\times (bm)^{r-2}\equiv a\times b^{r-2}\times m^{r-1}\mod r\\
\forall m\in\mathbb{Z}_r,m^{r-1}\equiv 1\mod r\\
\therefore a\times b^{r-2}\times m^{r-1}\equiv a\times b^{r-2}\times 1\equiv a\times b^{r-2}\mod r\]
위와 같이 기약분수가 아니더라도 같은 값을 가짐을 알 수 있습니다. 그래서 해야하는 것은 분자에 분모의 1000000005제곱한 값을 곱한 값의 1000000007로 나눈 나머지를 구한 후 이를 모두 더하는 것입니다. 1000000005제곱의 경우 반으로 쪼개서 곱하는 방식을 사용하여 로그의 시간 복잡도로 구할 수 있도록 합니다. 이제 각 분수에 대해 모두 더하여 1000000007로 나눈 나머지를 출력하면 됩니다.
PS알못 OrbitHv의 PS