bauua-and-amazing-series

Bauua is very fond of fibonacci numbers so one day he thought of an AMAZing series of which each term can be expressed as

f(n)=af(n-1) + bf(n-2) + c

Your task is to find nth term of the series.

Input:

t:testcases

Given: n , f(0), f(1), a, b & c

Output:

Value of nth term modulo MOD.

Constraints:

1 ≤ t ≤ 10^5

0 ≤ f(0)<f(1) ≤ 10^9

1 ≤ a,b,c ≤ 10^9

1 ≤ n ≤ 10^18

MOD= 10^9+7

SAMPLE INPUT
2
1 1 1 1 1 0
2 1 1 1 1 0

SAMPLE OUTPUT
1
1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: