FRSKT  Fibonacci recursive sequences (medium)
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^2 0 <= N <= 10^9 2 <= M <= 10^9
You would perhaps have a look, after, at the hard edition with more difficult constraints.
Edit 20170211, after compiler update. My old Python code ends in 0.08s. New TL.
hide comments
DK...:
20190605 23:52:20
I got AC in the harder version and the same code got WA for this problem, @Francky please, could you tell me what is happening with the testcases?


Gaurav Kumar Verma:
20141103 09:56:03
can anyone please provide sample test cases? m getting WA


[Lakshman]:
20140714 11:09:19
@SHUBHAM JAIN try to solve some easy Fibonacci problem then come to this.


SHUBHAM JAIN:
20140714 10:36:38
I am getting Segmentation fault runtime error in your compiler


[Lakshman]:
20140625 10:59:50
@Francky My new solution seems to be fine for all corner cases, but still getting WA.


[Lakshman]:
20140302 22:30:37
@Francky can you please check my solution why I am getting runtime error.


fR0DDY:
20130803 10:58:17
I am getting Runtime Error. Any hints for my solution or is my solution completely wrong? 

[Lakshman]:
20130512 07:06:57
Can you please give a bit hint where my solution fails .......


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130121 03:01:43
finally #1st place on this problem ;)


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120905 18:20:13
I'm getting WA... any clues/hints?

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