REC - Recurrence


Let F0 = 1. Fn = a*Fn-1 + b for n >= 1. Find Fn (mod M).

Input

The first line contains T the number of test cases. Each of the next T lines contains 4 space seperated integers a, b, n and M.

Constraints

T <= 20000
0 <= a, b, n <=  10^100
1 <= M <= 100000

Output

Output T lines, one corresponding to each test case.

 

Example

Input:
3
1 1 1 10
2 1 2 5
5 2 20 30

Output:
2
2
7


hide comments
biswajitk123: 2017-12-18 13:09:50

tle help! running loop till m

adi_1996: 2016-06-29 12:52:07

Submission id 17193542
Please check

utkarsh538: 2016-03-31 08:57:06

Getting NZEC in python 2.7....any problem?

Vamshider Reddy: 2015-06-18 21:51:39

what will be answer for M = 1, N = 0?

Devang Bacharwar: 2014-08-01 18:39:38

Runtime error NZEC using python 2.7. Is there any issue regarding this

[Lakshman]: 2014-06-20 19:02:11

Finally green!!!!!1

The Mundane Programmer: 2013-03-14 04:08:06

getting NZEC in python 2.5 after .26 seconds...... give some more test cases

The Mundane Programmer: 2012-06-12 18:43:53

getting NZEC in python 2.5 after .14 seconds...... give some more test cases

cjtoribio: 2011-07-23 06:00:05

@Miftakhul Khasanah
Check when M = 1 , N = 0


Added by:abhijith reddy d
Date:2009-11-14
Time limit:0.720s-2.516s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C++ 4.3.2 CPP14 C99 CLPS LISP clisp LISP sbcl D ERL FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE