AGS - Aritho-geometric Series (AGS)

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 consecutive numbers is constant. For example: 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 the same. For example: 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 example: let's say d = 1 and r = 2 and a(1) = 1, the 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' and '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 in 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. The first line will have 3 numbers 'a', 'd' and 'r'. The second line will have 2 numbers 'n' and '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

Explanation

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

Notes

The value of a, d, r, n and mod will be less than 108 and more than 0.

For every series, the second 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:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2012-06-25 16:02:54 Neeraj Bhat
@Deepak: why get NZEC in java....
my ID is: 7211023 pls help me

Last edit: 2012-06-25 16:03:19
2012-06-24 06:06:13 Aditya Pandey


Last edit: 2012-12-22 07:31:33
2012-06-05 04:02:27 Out0fbounds
Why I get NZEC in python?
<snip>
plzz help

Last edit: 2022-07-14 22:07:32
2012-05-28 11:22:24 Rishi Mukherje
Why I get NZEC in python?
Edit: My fault, sorry.

Last edit: 2012-05-28 20:46:11
2012-04-16 06:09:33 Prashant Gupta
plz chk my submission id
6810674
getting again & again wrong answer :(


-----
nothing wrong in problem... check the way u are calculating

GUESS YOUR MOD IS CAUSING ISSUES

Last edit: 2012-05-07 05:14:39
2012-04-13 04:05:27 Devil D
@Neeraj ..you are adding 'a' and multiplying by 'd' ..
You should add 'd' and Xply by 'r'
2012-04-11 15:20:34 Neeraj Bhat
@Deepak: why i'm getting WA, even for brute-force solution. I've checked for all possible errors. Plz tell where i'm wrong.
ID is:- 6815095

Last edit: 2012-04-12 08:55:11
2012-04-06 09:55:39 sanctity
Plz give some test cases which gives wrong answer.
ID - 6761874
2012-04-06 09:55:39 Neeraj Pradhan
Plz give some test cases which gives wrong answer.
ID - 6730172

Last edit: 2012-03-29 09:31:29
2012-04-06 09:55:39 (Tjandra Satria Gunawan)(曾毅昆)
@odyssey : maybe the problem is Divide or Mod by zero...

@Sidharth Gupta : you're right, thanks ;)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.