Expected Greatest Common Divisor

All submissions for this problem are available.
Several integers X_{0}, X_{1}, ..., X_{K1} are randomly chosen from some intervals. Namely, X_{0} is randomly chosen between A_{0} and B_{0}, inclusive, X_{1} is randomly chosen between A_{1} and B_{1}, inclusive, and so on. We are interested in the expected value of the greatest common divisor of the X_{i} which is the average of GCD(X_{0}, X_{1}, ..., X_{K1}) over all possible choices of X_{0}, X_{1}, ..., X_{K1}. In order to avoid floatingpoint precision issues, we instead use the following output method. Suppose the expected value of the greatest common divisor of all the X_{i} is P/Q, where P and Q are relatively prime positive integers. Find an integer N between 0 and 1000000006, inclusive, for which (P + Q * N) is divisible by 1000000007 = 10^{9} + 7.
Input
Input will begin with an integer T, the number of test cases. Each test case begins with an integer K, the number of integers to be chosen. K pairs of integers A_{i} B_{i} follow.
Output
For each test case, output the value N according to the problem statement. If multiple such values exist, print any one of them. If no such value exists, print 1.
Constraints
 1 ≤ T ≤ 50
 2 ≤ K ≤ 5
 1 ≤ A_{i} ≤ B_{i} ≤ 200000 (2 * 10^{5})
Sample Input
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
Sample Output
333333334 875000005 722222226 314159265
Explanation
Sample test 1. Here X_{0} is randomly chosen between 2 and 4, inclusive, and X_{1} is randomly chosen between 3 and 5, inclusive. The distribution of the greatest common divisor of X_{0} and X_{1} can be seen from the following table:
2  3  4  
3  1  3  1 
4  2  1  4 
5  1  1  1 
The expected value is therefore (1 + 3 + 1 + 2 + 1 + 4 + 1 + 1 + 1) / 9 = 15 / 9 = 5 / 3.
Since 5 + 3 * 333333334 = 1000000007, the answer is 333333334.
Sample test 2. Here each of X_{0}, X_{1}, X_{2} is randomly chosen between 1 and 2, inclusive. So we have 8 possibilities in all. The greatest common divisor is 2 when X_{0} = X_{1} = X_{2} = 2 and it is 1 in the 7 remaining cases. The expected value is therefore (1 * 7 + 2 * 1) / 8 = 9 / 8. Since 9 + 8 * 875000005 = 7000000049 = 7 * 1000000007, the answer is 875000005.
Sample test 3. Here P is 23 and Q is 18.
Sample test 4. Just enjoy the answer :)
Author:  pieguy 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/EXGCD 
Tags  cook29, easymedium, numbertheory, pieguy 
Date Added:  26112012 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 