I like short statements
and you should too
so here's the statement
without further ado
You are given $3$ positive integers $N, A, B$. You have to count the number of $N$ length positive integer arrays such that each of the elements of the array are divisors of $B$ and the greatest common divisor of the elements is$A$.
Since the count can be large you have to output it modulo $1000000007$. In other words, if the count is $X$, you have to output $X \bmod 1000000007$.
There will be $T$ independent testcases. First line of input will contain the positive integer $T$. Next $T$ lines will each contain three positive integers $N, A, B$ separated by spaces.
$1 \leq T \leq 100$
$1 \leq N \leq 10^{9}$
$1 \leq A, B \leq 10^{12}$
Output $T$ lines. The $i$ th line should have the answer for the $i$ th testcase.
Input | Output |
---|---|
3 2 2 16 1 5 15 3 6 15 | 7 1 0 |
In first testcase, there are $7$ such arrays $[2, 2], [2, 4], [2, 8], [2, 16], [4, 2], [8, 2], [16, 2]$