FIBOFUN - Fun with Fibonacci Series

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

hide comments
Prakhar Jain: 2012-08-28 08:29:04

m is never 0..!!!

Last edit: 2012-03-30 11:46:23
Andy: 2012-08-28 08:29:04

how to calculate if m=0 ?

my submission 6696276 is giving WA, but I can't find a test case where it fails

Last edit: 2012-03-21 10:26:22
Aman Kumar: 2012-08-28 08:29:04

@thanx Bruno..:)

Bruno Adami: 2012-08-28 08:29:04

got acc! check the forums for some sample input :)

Last edit: 2012-03-18 22:29:25
Pobut: 2012-08-28 08:29:04

There is something weird going on with some test cases... :)

spock: 2012-08-28 08:29:04

@pranay
give some test cases.

ginnipkj: 2012-08-28 08:29:04

@ Deepak S OR @Devil D ---- plz check why my submission ID 6671946 is getting WA

Pranay: 2012-08-28 08:29:04

nice problem :)

Last edit: 2012-03-17 11:16:51
spock: 2012-08-28 08:29:04

please give some difficult test cases

spock: 2012-08-28 08:29:04

Why am i getting the WA??..please check my submission id 6666736..


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