H. Good Luck Counting Mario ! (Purple)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the Mario Elite League!

You're preparing your kart for the upcoming races, the kart has $$$n$$$ item slots.

Mario Elite League

Each slot $$$i$$$ must be filled with an item of "Power Level" $$$A_i$$$.

To achieve peak performance, the array of Power Levels $$$[A_1, A_2, \dots, A_n]$$$ must satisfy the following conditions based on their combined effects:

  1. The Greatest Common Divisor (GCD) of all Power Levels must be exactly $$$g$$$. $$$$$$ \gcd(A_1, A_2, \dots, A_n) = g $$$$$$
  2. The Least Common Multiple (LCM) of all Power Levels must be exactly $$$l$$$. $$$$$$ \operatorname{lcm}(A_1, A_2, \dots, A_n) = l $$$$$$

Given integers $$$n, g, l$$$, Mario wants to count the number of distinct arrays $$$[A_1, A_2, \dots, A_n]$$$ satisfying these conditions.

Since the number of such arrays can be very large, output the answer modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line in each test case contains four space-separated integers $$$n$$$ ($$$1 \le n \le 10^6$$$), $$$g, l$$$ ($$$1 \le g, l \le 10^{12}$$$) — the number of items, the gcd, and the lcm respectively.

It's guaranteed that the sum of $$$g, l$$$ over all test cases does not exceed $$$1 \cdot 10^{12}$$$.

Output

For each test case, Print a single integer, the number of valid arrays modulo $$$10^9 + 7$$$.

Example
Input
3
2 2 6
3 1 4
6 6 24
Output
2
12
602