Joker planted a bomb in the city and challenged Batman to find the bomb before 11:30 PM :-) as it will explode at 11:30 PM. To make the situation little easy for batman Joker gives him a problem and answer to the problem is pseudo code for location.

consider the equation-

$F(x) : x^{2} + a * x + b$

$G(x) = ($ Product of all factors of $F(x)) modulo (1000000007)$ ,

where $F(x)$ is defined above.

G(x) is the pseudo code.

Help Batman calculating G(x) for a given set of values : a, b and x and help him save the city .

Input Format :

The first line contains one integer T , the number of integers. Each of the T test cases consists of 3 integers x , a and b respectively.

Output Format :

For each test case, output $G(x)$ , as mentioned in the problem statement.

Input Constraints :

$1 \le T \le 10$
$1 \le a,b \le 10^9$
$1 \le x \le 5*10^8$