F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

huntian oy

Time 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^a-j^a,i^b-j^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
2 1 2 3 100 2 3
 

Sample Output
0 101542
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-15 22:47:04, Gzip enabled