FRSKH - Fibonacci recursive sequences (hard)


Leo searched for a new fib-like problem, and ...
it's not a fib-like problem that he found !!! Here it is.

Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
and
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)

Example : we have FIB(6)=8, and FIB(8)=21.

Let F(K, N) a new function:
F(0, N) = N for all integers N.
F(K, N) = F(K-1, FIB(N) ) for K>0 and all integers N.

Example : F(2, 6) = F(1, FIB(6) ) = F(0, FIB( FIB(6) ) ) = FIB( FIB(6) ) = FIB(8) = 21

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are three integers: K, N, M.

Output

For each test case, print F(K, N),
as the answer could not fit in a 64bit container,
give your answer modulo M.

Example

Input:
3
4 5 1000
3 4 1000
2 6 1000

Output:
5
1
21

Constraints

1 <= T <= 10^3
0 <= K <= 10^18
0 <= N <= 10^18
2 <= M <= 10^18

K, N, M are uniform randomly chosen.

You would perhaps have a look, before, at the medium edition with easier constraints.

Edit(12/I/2015) My old Python code now ends in 2.19s using PY3.4 and cube cluster.

Edit(11/2/2017) Compiler updates ; my old Python3.5 code ends in 0.98s. New TL.


hide comments
[Lakshman]: 2014-07-03 06:36:24

This is the second hardest problem for me.
Thanks @Francky for this very good problem.

Last edit: 2014-07-03 08:17:36
[Lakshman]: 2014-06-27 06:22:32

@Francky can you please tell me if my approach is correct or not?

@Francky I am using cycle in pie(m) and computing the final answer for the length of the cycle but still wrong answer.
Please help

--ans(Francky)--> You have approx 15% of WA. You should use a better brute force to check your code...

---Lakshman->Finally accepted

Last edit: 2014-07-03 06:32:13
Michael Kharitonov: 2013-03-17 03:20:51

Why Pyramid?
--ans--> Pyramid was the lonely cluster available at the time of creating the problem. It add, it's true, several difficulties.
Congratulations for your result, you've found many mysteries of the problem.

Last edit: 2013-03-17 07:52:51
Niklas Baumstark: 2012-11-27 02:25:19

Great problem, thanks Francky!

Damian Straszak: 2012-09-02 12:00:41

Yay, finally accepted ;). Thank you for such an awesome problem (but hard as hell simultaneously ;)).
--ans--> good job and congrats. Thanks for the appreciation.

Last edit: 2012-08-24 16:45:51

Added by:Francky
Date:2012-08-19
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem