Σ

실제로 존재하는지는 접어두고, 삼면체 주사위를 굴린다고 하자. 각 면이 나올 확률은 모두 $1/3$로 같다. 한 면에 1, 다른 면에 2, 남은 면에 4가 적혀 있다면 굴렸을 때 나오는 수의 기댓값은 세 수의 평균인 $7/3$이다.

이 문제를 넓혀서 "$N$면체 주사위의 각 면에 적힌 수가 주어지고 각 면이 나올 확률이 모두 같을 때, 주사위를 굴리면 나오는 수의 기댓값은 얼마인가?"를 생각해 보자. 위 예시의 답을 소수로 적으면 $2.33333333\dots$인데, 무한한 자릿수를 다 출력할 수는 없으니 적당한 자리에서 끊어야 한다. 끊긴 소수를 채점 프로그램이 다시 읽어서 정답과 비교한다면 결과가 얼마나 부정확하겠는가? 그래서 답을 정확히 판별하려고 기약분수의 분모와 분자를 직접 출력하게 하던 시기가 있었다.

이제 주사위를 $M$개로 늘리자. $i$번째 주사위는 $N_i$면체이고 모든 면에 적힌 수의 합은 $S_i$이며, 주사위마다 각 면이 나올 확률은 같다. 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제다. 확률변수 $X$의 기댓값을 $E(X)$로 쓰면 기댓값의 선형성에 의해 두 확률변수 $X$, $Y$에 대해 $E(X + Y) = E(X) + E(Y)$가 성립하므로, 답을 다음과 같이 간단히 적을 수 있다.

$\frac{S_1}{N_1} + \frac{S_2}{N_2} + \dots + \frac{S_M}{N_M}$

각 주사위에서 나오는 수의 기댓값을 모두 더하면 답이 된다. 이 답을 정확히 출력하려고 모든 분수를 통분한다고 해 보자. 분모와 분자의 값이 어느 범위까지 치솟겠는가? 분모와 분자를 그대로 들고 있으면 두 분수의 합을 구할 때 적정한 범위 안에서 계산해낼 수 없다는 문제에 부딪힌다. "그러면 분모와 분자를 어떤 모듈러 위에서 들고 있으면 되지 않을까?"라고 생각할 수 있지만, 그러면 분모와 분자를 약분할 수가 없다. 그래서 분수를 모듈러 위의 정수 하나로 들고 있는 방법을 쓴다.

어떤 분수를 기약분수로 나타냈을 때 $a/b$이면, 이 분수를 $a \times b^{-1} \bmod X$ ($X$는 소수)로 대신 계산한다. 여기서 $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다.

$b$의 모듈러 곱셈에 대한 역원 $b^{-1}$은 대체 어떤 수인가? 다음 성질을 만족하는 정수다.

$b^{-1} \times b \equiv 1 \pmod X$

소수 모듈러에서만 성립하는 페르마의 소정리에 의해 $b^{X-1} \equiv 1 \pmod X$가 성립하므로, $b^{X-2} \equiv b^{-1} \pmod X$ 역시 성립함을 알 수 있다.

이해를 돕기 위해 $X$를 11로 두고 $Q = 7/3$을 계산해 보자. $3^{-1} \equiv 4 \pmod{11}$이므로 $Q \equiv 7 \times 4 \equiv 6 \pmod{11}$이다. 이 $Q$에 3을 곱한 다음 11로 나눈 나머지를 구하면 7이 나오므로, 정수 6이 $7/3$을 제대로 담고 있음을 알 수 있다.

분수를 이렇게 나타내면 두 분수의 덧셈, 뺄셈, 곱셈은 모듈러 위에서 두 정수를 계산하듯 처리하고, 나눗셈은 나누는 분수의 곱셈에 대한 역원을 구해 모듈러 위에서 곱하는 것으로 처리한다. 분수를 정확히 출력하려고 통분하거나 기약분수로 만드는 골치아픈 일을 할 필요가 없어진다.

물론 이 방법에도 문제는 있다. 앞의 예에서 $7/3$을 6으로 저장했지만 $6/1$도 6으로 저장한다. 서로 다른 두 분수를 모듈러 위에서 같은 정수로 저장하니, 정확히 판별한다는 목적에 어긋난다. 분모가 $X$를 소인수로 가질 때에는 역원을 계산할 수 없어서 모듈러로 나타낼 수 없다는 문제도 있다. 이런 문제를 줄이려고 모듈러를 1,000,000,007 같은 큰 소수로 잡는다. 서로 다른 두 분수가 같은 정수로 나타날 확률이 낮아지고, 분모가 가질 수 있는 소인수의 범위도 넓어진다. 그는 그래도 이 방식이 가장 정확하다고 생각하게 되었다.

이제 이 방식으로, 주사위가 $M$개 있고 $i$번째 주사위가 $N_i$면체이며 모든 면에 적힌 수를 더한 값이 $S_i$일 때, 모든 주사위를 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구해 보자.

첫째 줄에 주사위의 수를 나타내는 정수 $M$ ($1 \le M \le 10^4$)이 주어진다.

이어지는 $M$개의 줄은 각 주사위의 정보를 나타낸다. 그중 $i$번째 줄 ($1 \le i \le M$)에는 $N_i$와 $S_i$ ($1 \le N_i, S_i \le 10^9$)가 공백으로 구분되어 주어진다.

모든 주사위를 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타냈을 때 $a/b$가 된다면 $a \times b^{-1}$을 1,000,000,007로 나눈 나머지를 대신 출력한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

기댓값이 $7/3$인 경우, 모듈러가 11에서 1,000,000,007로 바뀌면 출력할 정수도 달라진다. 그래도 그 정수에 3을 곱한 다음 1,000,000,007로 나눈 나머지는 7이 된다.