시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 8 7 70.000%

문제

크기가 K인 두 수열 A와 B가 주어진다. 수열 X는 A와 B를 이용해서 만들 수 있으며, Xi는 Ai보다 크거나 같고, Bi보다 작거나 같은 정수 중에서 랜덤하게 고른다. 

수열 A와 B가 주어졌을 때, GCD(X0, X1, ..., XK-1)의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 50)가 주어진다.

각 테스트 케이스의 첫째 줄에는 K (2 ≤ K ≤ 5)가 주어진다. 다음 K개의 줄에는 Ai와 Bi가 한 줄에 하나씩 주어진다. (1 ≤ Ai ≤ Bi ≤ 200000)

출력

문제의 정답이 P/Q인 경우에, 109+7로 나누어 떨어지는 P+Q×N을 찾고, 그 때 N (0 ≤ N ≤ 109+6)을 첫째 줄에 출력한다. 만약, N이 존재하지 않으면 -1을 출력한다.

예제 입력 1

4
2
2 4
3 5
3
1 2
1 2
1 2
3
1 12
1 12
1 12
2
2700 2701
2612 2724

예제 출력 1

333333334
875000005
722222226
314159265

힌트

출처