Harry knows that one of the Horcruxes is hidden inside Bellatrix Lestrange's vault at Gringotts. He must destroy it to weaken Lord Voldemort. However, he faces a small challenge : the vault requires a special code to open it - the Fibcode.

The Fibcode is an improved form of the common fibonacci sequence :

Fib(N) = P * Fib(N-1) + Q * Fib(N-2) : if N>=2
Fib(0) = 0, Fib(1) = 1

Given the values of N,P,Q obtain the value of Fib(N).

Since the result can be very large, print it modulo (10^9 + 7).

Input
The first line contains an integer T, the number of testcases.
Each of the next T lines contains three integers - N, P, Q

Output
Print the value of Fib(N) for given values of N, P, Q for each testcase in a new line.

Constraints
1 <= T <= 10^6
0 <= N, P, Q <= 10^8