Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem B: Fibonacci GCD

Problem B: Fibonacci GCD

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 22  Solved: 8
[Submit][Status][Web Board]

Description

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.

Input

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)

Output

For each test case output one line contain answer.

Sample Input

2
9 4 6 6
1 1 1 1

Sample Output

2
1

HINT

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

[Submit][Status][Web Board]