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