FIBOFUN  Fun with Fibonacci Series
Fibonacci series is a series in which every element is sum of previous 2 elements.
first 2elements are 0,1 and the series goes like 0,1,1,2,3,5,8,13 ........
What if you were given 2 random numbers as the starting of the series and u follow the same rule as the fibonacci rule.
for eg. if you were given 2 and 2 .. the series would become
2 2 4 6 10 16 26 .........
Now ur task is Simple ...
You will be given 2 numbers a & b .. the first and second term of the series..
you need to calculate the sum of first n numbers of the series so formed..
Since the numbers can be big you need to print the result mod some number 'M' provided in the input.
Input
first line will have single number 't'  number of test cases.
each test case will have 4 numbers a,b,n & M
a first number of the series
b second number of the series
n calculate the sum till n numbers
M print the result mod M
Output
single number for each case  sum of n terms mod M
Example
Input: 2
2 2 10 21
1 3 10 21
Output: 13
4
Explanation  for first case series is 2 2 4 6 10 16 26 42 68 110 .. Sum is 286.. o/p = 286%21 = 13NOTE 
Number of test cases <=100.
0 <= a,b,m <= 10^81 <= n <= 10^8actually n ranges from 1 to 10^8
hide comments
Shubham Jadhav:
20170512 04:10:06
AC in one go :) 

Ankur Singh:
20160717 08:38:03
Don't forget to take the MOD, even for small cases of n like 1, 2. 

Satyam Mishra:
20150613 10:05:20
Nice problem..


__hk__:
20150609 11:57:26
Finally AC..!!


ALISHA:
20141224 21:30:20
Never matters whether it's in tutorial or classical section. All that matters is the bliss of getting green band in first attempt.Rest is all greed my friend.:P Last edit: 20141224 21:31:14 

success:
20141210 08:26:05
plz check my code why wrong answer.?


Francky:
20140124 18:33:28
I very well know Fibonacci variation's problems here at spoj, and I can confirm that this one don't give new materials. It is a tutorial problem for several reasons. I don't say it is an easy problem. Please trust EB members in their actions ; stop asking for classical. 

Somesh Maurya™:
20140124 17:01:23
C'mon this isn't a tutorial problem... Move it to classical please... 

Somesh Maurya™:
20140124 17:00:31
What if m=0?? 

Arika Saputro:
20130509 13:47:29
why my code giving WA?

Added by:  Devil D 
Date:  20120315 
Time limit:  1s 
Source limit:  10000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 