극한의 gcd 합

정수 상수 $a_1, b_1, \dots, a_n, b_n$의 값이 주어진다. 아래 코드를 끝까지 실행했을 때 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는 인자로 받은 $x_1, x_2, \dots, x_n$의 최대공약수를 돌려주는 함수이고, sum은 아무리 큰 정수라도 담는 변수다.

너무 쉬워 보이나요? 저도 그렇게 생각합니다.

첫째 줄에 자연수 $n$이 주어진다.

다음 $n$개 줄 가운데 $i$번째 줄에는 $a_i$와 $b_i$가 공백으로 구분되어 주어진다.

$1 \le n \le 10\,000$, $1 \le a_i \le b_i \le 1\,000\,000$이다.

C/C++에는 아무리 큰 정수라도 담는 자료형이 없으므로, sum의 값을 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.