FRSKH  Fibonacci recursive sequences (hard)
Leo searched for a new fiblike problem, and ...
it's not a fiblike 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(N1) + FIB(N2)
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(K1, 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]:
20140703 06:36:24
This is the second hardest problem for me.


[Lakshman]:
20140627 06:22:32
@Francky can you please tell me if my approach is correct or not?


Michael Kharitonov:
20130317 03:20:51
Why Pyramid?


Niklas Baumstark:
20121127 02:25:19
Great problem, thanks Francky! 

Damian Straszak:
20120902 12:00:41
Yay, finally accepted ;). Thank you for such an awesome problem (but hard as hell simultaneously ;)).

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