## 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:31 1 1 102 1 2 55 2 20 30Output:227`

hide comments
 < Previous 1 2 Next > kamina01: 2020-04-23 11:10:16 AC...in one go!!! use matrix modular exponentiation with big integer.... nadstratosfer: 2020-02-15 09:01:47 Recalling that 1%1 = 0 took me 40mins. Be careful. biswajitk123: (T=20000) * 100000 = 2*10^9. That can't possibly fit in TL. Last edit: 2020-02-15 09:03:31 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

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