

huntian oyTime Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2583 Accepted Submission(s): 629 Problem Description One day, Master oy created a new function to celebrate his becoming a 'huntian' in majsoul. $f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^aj^a,i^bj^b)[gcd(i,j)=1]\%(10^9+7)$ Given n, a and b, Master oy wanted Newbie jj who was still a 'chuxin' to answer the value of $f(n,a,b)$. Input There are multiple test cases. The first line contains an integer T, indicating the number of test cases. For each test case, there are three positive integers n, a and b which are separated by spaces. It's guaranteed that $a$ and $b$ are coprime. $1 \le n,a,b \le 10^9$ $T=10^4$, but there are only 10 test cases that n is over $10^6$. Output For each test case, an integer in one line representing your answer. Sample Input
Sample Output
Source  
