Given N, x, y, z. Find the GCD of x*F(n) + y*F(n+1) and z*F(n) .Where F(n) is the n Fibonacci number:
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).
Since the answer is very big, please modulo 1000000007.

The first line contains one integer T, indicates the total test cases. Each test case contains four integer N, x, y, z.

(0<=N<=1e9, 0<=x,y,z<=1000,T = 10000)

For each test case output one line contain answer.

GCD(n, 0) = GCD(0, n) = n;