AGS  Arithogeometric Series (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
dthe 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 ..
hide comments
Rajat Singh:
20150818 11:30:34
excellent one!!!!!learned a very unique concept!!!!!!!!!! 

Babu:
20150730 18:01:26
where are the fucking constraints??? _


Bhuvnesh Jain:
20150719 09:40:56
What a brilliant question! Finally ac after long struggle. New method for sum of GP.... Can't believe it was AC in 0.00 sec.... phew 

ABHISHEK004:
20150226 22:57:27
tried after 2 years ...


i need you:
20141229 21:09:06
very nice problem...wasted 2 days


Aditya Paliwal:
20141217 23:10:11
Took just 5 mins to derive formula but 4 hours to code it! Amazing problem! Seemed like I have solved similar problems before but I had to learn something new :) Awesome! Last edit: 20141217 23:10:38 

Prateek chandan:
20140825 23:49:28
I have tried for all test cases but still WA


Bhavik:
20140616 21:24:01
Last edit: 20140624 10:25:40 

Smriti Vashisth:
20140522 16:03:32
getting WA despite checking all the cases


Piyush Raman Srivastava:
20140122 13:28:32
wrong assumptions by problem solvers and an awesome mathematics!! Thanx a lot @Devil D :)

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