GCD, Divisor, Count!

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$.

Input

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

Output $T$ lines. The $i$ th line should have the answer for the $i$ th testcase.

Sample

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]$