Lotte Giants and Gahui
Time limit0.5sMemory limit512 MB
Count length-n sequences of positive integers whose gcd is G and lcm is L, printing each answer modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Math, Number theory, Combinatorics, Dynamic programming
- Solved
- No attempts yet
Problem
On July 28 of last year, as always during baseball season, Gahui was watching Lotte baseball. Then suddenly, T math problems appeared on the TV screen.
Startled with the bottom of the 9th inning just beginning, Gahui asked you to quickly solve the T [Problems] shown on the TV screen.
[Problem] Find the number of sequences that satisfy the following conditions.
- The length of the sequence is n.
- Every number in the sequence is a natural number greater than 0.
- The greatest common divisor of the numbers in the sequence is G.
- The least common multiple of the numbers in the sequence is L.
A [Problem] is displayed on the TV screen as a single line n G L.
Input
The first line gives the number of problems T that appeared on the TV screen.
From the second line to the T+1-th line, information about the problems shown on the TV screen is given in the format n G L. These numbers are separated by spaces.
Output
For each problem, print the answer modulo 109+7 (1,000,000,007), one per line.
Constraints
- 1 ≤ T ≤ 100
- 2 ≤ n ≤ 106
- 1 ≤ G, L ≤ 109