FIBFUNCH - Fun with Fibonacci Series (Challenge)

no tags 

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 your 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 = 13
NOTE -
Number of test cases <=100.
0 <= a,b<= 10^8
1 <= n,m <= 10^8
actually n ranges from 1 to 10^8

hide comments
rainy jain : 2016-06-03 08:00:40

@Devil D any tricky test case,getting WA on 9th one?

Last edit: 2016-06-03 08:03:16
hmp: 2016-05-23 08:27:17

9th test case and then WA :( :(

edit : ans = (ans+m)%m.

Last edit: 2016-05-23 10:24:08
lodka: 2016-05-11 10:46:21

Why in second case the answer is 4 if series will be 1 3 4 7 11 18 29 47 76 123 and summ of it is 319?

Saurabh Mishra: 2014-11-30 12:56:14

whats the problem with 9th case???

Saurabh Mishra: 2014-11-30 12:56:14

whats the problem with 9th case???

pinki: 2014-09-02 20:09:05

getting wa on 9th test case :(

[Lakshman]: 2014-06-28 14:28:03

@just_do_it Its curious, how did you solve FIBOSUM?

Abhishek Kumar: 2014-06-28 12:43:56

plz some one check my code.i dont know y m getting WA...:/
http://ideone.com/G7KhVR

Ouditchya Sinha: 2013-06-24 19:26:00

@Atul Kumar Verma: Answer for your test case is 29568. :)

Atul Kumar Verma: 2013-06-12 06:16:43

Can anybody tell me output for this case:
100000000 100000000 100000000 123456


Added by:Devil D
Date:2012-04-26
Time limit:1s
Source limit:4000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:BF C CSHARP C++ 4.3.2 CPP C99 D FORTRAN ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS PRLG-swi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:Own