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
Testcase 1:
Fib(2) = 2*1 + 5*0 = 2
Fib(3) = 2*2 + 5*1 = 9
Answer is 9 .
Testcase 2:
Fib(2) = 1*1 + 3*0 = 1
Fib(3) = 1*1 + 3*1 = 4
Fib(4) = 1*4 + 3*1 = 7
Answer is 7 .
