FIBOSQRT - Fibonacci With a Square Root

FIBONACCI is the recursive sequence that is given by: F(n)=F(n-1)+F(n-2) with F(0)=0 and F(1)=1.

In this problem we define FIBOSQRT that is given by: Fs(n)=Fs(n-1)+Fs(n-2)+2*SQRT(3+Fs(n-1)*Fs(n-2)) with Fs(0) and Fs(1) are given in the input file.

It's guaranteed that SQRT(3+Fs(n-1)*Fs(n-2)) is always an integer. Wink I've proved it by math theorem.

Now your task is to find Fs(n). Since the number can be big you have to find the result mod M.

Input

The first line is an integer T(1 ≤ T ≤ 111,111), denoting the number of test cases. Then, T test cases follow.

For each test case, there are four integers Fs(0), Fs(1) (1 ≤ Fs(0) ≤ Fs(1) < 106), M (1 ≤ M < 109), and n (0 ≤ n < 1018) written in one line, separated by space.

Output

For each test case, output Fs(n) mod M.

Example

Input:
2
1 1 10 5
2 3 100 6

Output:
4
82

Explanation:

Case #1:
  • Fs(0)=1
  • Fs(1)=1
  • Fs(2)=1+1+2*SQRT(3+1*1)=6
  • Fs(3)=6+1+2*SQRT(3+6*1)=13
  • Fs(4)=13+6+2*SQRT(3+13*6)=37
  • Fs(5)=37+13+2*SQRT(3+37*13)=94

The answer is: 94 mod 10 = 4.

Case #2:
  • Fs(0)=2
  • Fs(1)=3
  • Fs(2)=3+2+2*SQRT(3+3*2)=11
  • Fs(3)=11+3+2*SQRT(3+11*3)=26
  • Fs(4)=26+11+2*SQRT(3+26*11)=71
  • Fs(5)=71+26+2*SQRT(3+71*26)=183
  • Fs(6)=183+71+2*SQRT(3+183*71)=482

The answer is: 482 mod 100 = 82.

Notes

File #1: More than 100,000 random test cases (test your program speed Laughing)

File #2: Less than 10 test cases (tricky test cases that might give you WA Tongue out)

Time Limit ≈ 8*(My Program Top Speed)

Warning: large Input/Output data, be careful with certain languages

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2012-08-30
Time limit:1.063s-6.147s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2016-06-23 21:37:24 ASHUTOSH DWIVEDI
Now that is known as typical ''TJANDRA'' problem tested all the maths :P


Last edit: 2016-06-23 22:01:16
2015-12-26 05:52:21 ashish kumar
How to optimise my code to take less than 1 sec to run . Currently it is taking 3 sec.
2015-08-10 21:17:35 Pranav Rai
@tjandra Can you see my solution I am constantly getting a TLE.

Last edit: 2015-08-10 21:18:53
2015-01-22 22:58:51 Soma
@(Tjandra Satria Gunawan) awesome problem..../ it was fun doing this problem.. lots of maths...
2014-12-27 06:25:47 pranjuldb
Maths at its best :D

Last edit: 2014-12-27 09:58:59
2014-12-23 04:19:42 [Lakshman]
@Francky Congrats , you got AC. I think My algorithm is fine but my I/O are slow. I need to learn Fast IO in python.
--Francky--> No, this problem isn't IO related, read and write is very % of process. We need to try several tricks for the exponentiation, and choose the best for Python ; not all suit. It is hell to find the good mix, and very instructive too. And congrats for your coprime #1. ;-)

-Lakshman-->Thanks @Francky.

Last edit: 2014-12-23 04:35:49
2014-12-21 20:54:38 Francky
@Lakshman: I'm trying too to get AC with Python with a new fast code. I can, for now output 50% of input in 28.86s ; I need a good 10% speed up. It will be very hard to get AC here. Congrats to Mitch for that.
Edit : 27.10s for 50%. 48.71s for 90%.
Edit2 : I think I got it, but there should be one (or more) empty line at the end of input... or something strange.
Edit3 : that was that. Warning : extra-large Input/Output data, be careful with certain languages. ;-)

Last edit: 2014-12-23 04:13:42
2014-12-21 20:51:13 [Lakshman]
@(Tjandra Satria Gunawan)(曾毅昆) My best time with cpp is 1.63 but same algorithm gives TLE in PYTHON.
2013-08-19 17:36:51 Prateesh Goyal
@Tjandra
Can you provide some test cases
2013-07-03 12:29:07 wisfaq
@Mitch:
Thanks for that.

Last edit: 2013-07-03 12:30:54
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.