Sphere Online Judge

SPOJ Problem Set (classical)

10966. Aritho-geometric Series (AGS)

Problem code: AGS


Arithmatic and geometric Progressions are 2 of the well known progressions in maths.

Arithmatic progression(AP) is a set in which the difference between 2 numbers in constant. for eg, 1,3,5,7,9 .... In this series the difference between 2 numbers is 2.

Geometric progression(GP) is a set in which the ratio of 2 consecutive numbers is same. for eg, 1,2,4,8,16.... In this the ratio of the numbers is 2.

.....

What if there is a series in which we multiply a(n) by 'r' to get a(n+1) and then add 'd' to a(n+1) to get a(n+2)...

For eg .. lets say d=1 and r=2 and a(1) = 1..

series would be 1,2,4,5,10,11,22,23,46,47,94,95,190 ......

We add d to a(1) and then multiply a(2) with r and so on ....

 

Your task is, given 'a' , 'd'  &  'r' to find the a(n) term .

sicne the numbers can be very large , you are required to print the numbers modulo 'mod' - mod will be supplied int the test case.

Input

first line of input will have number 't' indicating the number of test cases.

each of the test cases will have 2 lines

firts line will have 3 numbers 'a' ,'d'  and   'r'

2nd line will have 2 numbers 'n' & 'mod'

a- first term of the AGS

d-the difference element

r - the ratio element

n- nth term required to be found

mod- need to print the result modulo mod

Output

For each test case print "a(n)%mod" in a separate line.

Example

Input:
2
1 1 2
13 7
2 2 2
10 8

 Output:

1
6


Description - for the first test case the series is 1,2,4,5,10,11,22,23,46,47,94,95,190..
13th term is 190 and 190%7 = 1

Note - the value of a , d , r , n & mod will be less than 10^8 and more than 0.
for every series 2nd term will be a+d and third term will be (a+d)*r .. and so on ..

Added by:Devil D
Date:2012-03-09
Time limit:0.5s
Source limit:10000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:Own

hide comments
2014-06-16 21:24:01 Bhavik


Last edit: 2014-06-24 10:25:40
2014-05-22 16:03:32 Smriti Vashisth
getting WA despite checking all the cases
plz help Devil D
https://ideone.com/wRd0jo

Last edit: 2014-06-08 12:18:51
2014-01-22 13:28:32 Piyush Raman Srivastava
wrong assumptions by problem solvers and an awesome mathematics!! Thanx a lot @Devil D :)
2013-12-30 12:36:57 shiva_hellgeek
Got 15 WAs in summer vacations.
Now AC in 1 go in Winters ;)
Really enjoyed solving this one.
2013-08-05 08:20:46 darryl
It seems that the testcase lacks condition where a+d is bigger than the mod.
2013-07-18 09:47:52 Hasil Sharma


Last edit: 2013-11-11 18:42:32
2013-07-04 12:57:56 pm
getting wa in python at running(4),
nd tle in C(same algo)at running(5) ... pls help ?? if dere any tricky case.....

Last edit: 2013-07-04 13:12:04
2013-06-19 15:20:42 Shubham Gupta
Getting WA in the 5th case, can anyone suggest something where I am going wrong? pls pls
2013-06-19 14:41:51 Man Mohan Mishra
awesome problem.....
maths involved !!
got AC in 2nd attempt :)
2013-06-08 08:46:45 Ankur
Finally Finally that green light !!! :) :)
Learnt a new thing about % ..
Great Problem.. Thanks @Devil D

Last edit: 2013-06-08 11:49:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.