Σ

Set aside whether such a thing exists, and suppose you have a three sided die that you roll. Each face comes up with the same probability $1/3$. If one face reads 1, another reads 2, and the last reads 4, what is the expected value of the number you roll? It is simply the average of the three, $7/3$.

Widen the question a little: "given the number written on each face of an $N$ sided die, where every face is equally likely, what is the expected value of the number you roll?" Written as a decimal, the answer to the example above is $2.33333333\dots$. Infinitely many digits cannot be printed, so the output gets cut off somewhere, and if a judging program reads that truncated decimal back and compares it against the answer, how inaccurate is the result? To judge the answer exactly, there was a period when problems asked you to reduce the fraction to lowest terms and print its numerator and denominator directly.

Now widen it further. There are $M$ dice. Die $i$ has $N_i$ faces and the numbers on all of its faces add up to $S_i$, and for each die every face is equally likely. Find the expected value of the sum of the numbers you get when you throw every die once. Writing $E(X)$ for the expected value of a random variable $X$, linearity of expectation gives $E(X + Y) = E(X) + E(Y)$ for two random variables $X$ and $Y$, so the answer can be written simply as follows.

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

Adding up the expected value of each die gives the answer. To print that answer exactly, suppose you put all of the fractions over a common denominator. How large do the numerator and the denominator climb? Holding the numerator and the denominator as they are, you run into a sum of two fractions that cannot be computed inside any reasonable range. You might think "then why not hold the numerator and the denominator modulo something?", but then the fraction can no longer be reduced. So the fraction is instead held as a single integer in modular arithmetic.

If a fraction reduced to lowest terms is $a/b$, compute it instead as $a \times b^{-1} \bmod X$, where $X$ is a prime. Here $b^{-1}$ is the modular multiplicative inverse of $b$.

What kind of number is that inverse $b^{-1}$? It is the integer satisfying the following.

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

By Fermat's little theorem, which holds for a prime modulus, $b^{X-1} \equiv 1 \pmod X$, and therefore $b^{X-2} \equiv b^{-1} \pmod X$ holds as well.

For a concrete look, set $X$ to 11 and compute $Q = 7/3$. Since $3^{-1} \equiv 4 \pmod{11}$, we get $Q \equiv 7 \times 4 \equiv 6 \pmod{11}$. Multiplying this $Q$ by 3 and taking the remainder modulo 11 gives 7, so the integer 6 does hold $7/3$ properly.

With fractions represented this way, addition, subtraction and multiplication of two fractions are handled as arithmetic on two integers modulo $X$, and division is handled by taking the multiplicative inverse of the divisor and multiplying by it modulo $X$. The painful work of finding a common denominator or reducing a fraction just to print it exactly goes away.

The method has its own problems. In the example above $7/3$ was stored as 6, but $6/1$ is stored as 6 too. Two different fractions are stored as the same integer modulo $X$, which defeats the goal of judging exactly. Another problem is that a denominator having $X$ as a prime factor has no inverse, so it cannot be represented at all. To reduce these problems, the modulus is taken to be a large prime such as 1,000,000,007. That lowers the chance of two different fractions landing on the same integer and widens the range of prime factors a denominator may have. He came to think this is still the most accurate method available.

Now solve the problem in this form: there are $M$ dice, die $i$ has $N_i$ faces and the numbers on all of its faces add up to $S_i$, and every face of a die is equally likely. Find the expected value of the sum of the numbers obtained by throwing every die once.

The first line contains an integer $M$ ($1 \le M \le 10^4$), the number of dice.

Each of the next $M$ lines describes one die. The $i$-th of those lines ($1 \le i \le M$) contains $N_i$ and $S_i$ ($1 \le N_i, S_i \le 10^9$), separated by a space.

Print the expected value of the sum of the numbers obtained by throwing every die once. For exact judging, if the answer reduced to lowest terms is $a/b$, print $a \times b^{-1}$ modulo 1,000,000,007 instead. Here $b^{-1}$ is the modular multiplicative inverse of $b$. In this problem the answer exists for every possible input.

When the expected value is $7/3$, changing the modulus from 11 to 1,000,000,007 changes the integer you print. Multiplying that integer by 3 and taking the remainder modulo 1,000,000,007 still gives 7.