SPOJ.com - Problem FIBFUNCH

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

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Avinash Thummala: 2013-04-13 19:00:13 @Problem Setter: Is the value of M (or m) same for all the 't' cases ? Is there any relation between all the values of 'm' ?
	Kevin Sebastian: 2013-04-13 19:00:13 getting WA dont knw why..pls check..my soln id 8340276
	15972125841321: 2013-04-13 19:00:13 plz check , its giving wa in 9th test case my sub id is ....7160787 i got same accepted at tutoria section Last edit: 2012-06-16 16:35:20
	devu: 2013-04-13 19:00:13 @Devil D:I got zero points for solving it please look at it. my submission id is 7116902. Last edit: 2012-06-09 11:50:10
	Aditya Pande: 2013-04-13 19:00:13 got AC finally Last edit: 2012-10-07 19:55:11
	GAP: 2013-04-13 19:00:13 what to do when m=0 ---- m will not be 0 Last edit: 2012-05-07 04:52:52
	Mitch Schwartz: 2013-04-13 19:00:13 I don't know what quality standards should be used for shortening problems in challenge section, or if there's a quota and we simply don't want to have too many shortening problems regardless of quality, but for me these past three problems are interesting to shorten; there are some specific insights that work out nicely and lead to significantly shorter code.
	numerix: 2013-04-13 19:00:13 @Problemsetter: I cannot follow your arguments according the language restrictions. Even among the languages you allowed there are some that have advantages in shortening compared to others. And: Why exclude e.g. Pascal or Pike? Can you write short code with those languages? And: With the same argument you should exclude fast languages e.g. from challenging problems like PRIC, which would be ridiculous. According to my objections against more copies of classical problems with shortening target: Of course shorting a code is different to get a classical problem AC, but "challenge" section is much more than shortening and adding more of those shortening problems reduces the high standards of this section. So why not move at least two of your latest shortening problems to partial section? Last edit: 2012-04-26 19:34:07
	numerix: 2013-04-13 19:00:13 I don't think, it's a good idea to publish more and more copies of classical problems to challenging section and increase the number of shortening problems even more. Even yet there are too many shortening problems. If you like shortening, try the SPOJ shortening contest: www.spoj.pl/SHORTEN ------------------ Got your point. But thing is finding a solution an finding a short solution are different things & we can have different problems for both Last edit: 2012-04-26 17:58:00
	Mitch Schwartz: 2013-04-13 19:00:13 Oy, it said all languages were allowed at first, so I spent time writing a solution in Python. It's probably best to wait a little before unhiding problems, to allow SPOJ time to update its cache. (Assuming you changed settings just before unhiding it.) ------------- Yes that i changed the languages just before unhiding. Last edit: 2012-04-26 17:55:56

Submit solution!

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