Xtreme gcd sum

Time limit4sMemory limit256 MB

Summary

Add the gcd of every tuple formed by picking one integer from each of the n given intervals and print the total modulo 1,000,000,007.

Level: Hard8 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

You are given the integer constants $a_1, b_1, \dots, a_n, b_n$ . Run the code below to the end and find the value that is finally stored in sum.

sum = 0;
for (x1 = a1; x1 <= b1; x1++)
    for (x2 = a2; x2 <= b2; x2++)
        ...
            for (xn = an; xn <= bn; xn++)
                sum = sum + gcd(x1, x2, ..., xn);

gcd returns the greatest common divisor of its arguments $x_1, x_2, \dots, x_n$ , and sum is a variable that holds an arbitrarily large integer.

Looks too easy? I think so too.

Input

The first line contains a natural number $n$ .

The $i$ -th of the next $n$ lines contains $a_i$ and $b_i$ , separated by a space.

$1 \le n \le 10\,000$ and $1 \le a_i \le b_i \le 1\,000\,000$ .

Output

C and C++ have no data type that holds an arbitrarily large integer, so print the value of sum modulo $1\,000\,000\,007$ on one line.

Examples3

Example 1
Input
```
3
1 7
1 5
1 3
```
Expected output
```
115
```
Example 2
Input
```
1
1 1
```
Expected output
```
1
```
Example 3
Input
```
2
4 6
9 12
```
Expected output
```
28
```