AGSCHALL - Aritho-geometric Series (AGS) (Challenge)

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

Arithmetic 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 .

since 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-04-24
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:BF C CSHARP C++ 4.3.2 CPP C99 LISP sbcl D FORTRAN ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS PRLG-swi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:Own

hide comments
2013-04-13 18:58:01 (Tjandra Satria Gunawan)(曾毅昆)
it's hard to shorten the ~400B code from my old submission to ~200B @_@ take about 2 hours...
2013-04-13 18:58:01 Aditya Pande
nice problem

Last edit: 2012-10-23 09:00:34
2013-04-13 18:58:01 demacek
Any reason for that strange language restriction?
people knowing python,ruby,C & perl have advantage .
Wanted to allow pascal people to have a chance
2013-04-13 18:58:01 numerix
Any reason for that strange language restriction?


====
people knowing python,ruby & perl have advantage . Wanted to allow C people to have a chance

Re( Xeronix ) : Then allow C only. Because i believe Go, pike, PHP users also have the advantages you are referring to.


-------
Done .....

Last edit: 2012-04-27 05:39:11
2013-04-13 18:58:01 XeRoN!X
@Author, set Assessment type = minimise score.

==============
Done....

Last edit: 2012-04-25 18:32:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.