Xtreme gcd sum Batch Compilation commands

간단한 문제입니다. 정수 상수인 $a1, b1, ..., an, bn$의 값이 주어질 때 아래 소스코드를 실행하면 sum변수에 최종적으로 어떤 값이 저장되는지 구해주세요.

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

너무 간단한가요? 저도 그렇게 생각해요. (웃음)

여기서 gcd함수는 x1, x2, ..., xn의 최대공약수를 구하는 함수입니다.

입력 형식

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

이후 $n$개의 줄의 $i$번째 줄에는 $ai, bi$($1 \le ai \le bi \le 1,000,000$)가 공백으로 구분되어 주어진다.

쉬운 문제에서는 $1 \le n \le 10$인 입력이 주어진다.

어려운 문제에서는 $1 \le n \le 10,000$인 입력이 주어진다.

출력 형식

C/C++에서는 very big int형 같은 좋은 변수형이 없으므로 sum의 값을 $1,000,000,007$로 나눈 나머지를 출력한다.

입력

3
1 7
1 5
1 3

출력

115