FRSKT - Fibonacci recursive sequences (medium)

no tags 

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^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 2017-02-11, after compiler update. My old Python code ends in 0.08s. New TL.


hide comments
Gaurav Kumar Verma: 2014-11-03 09:56:03

can anyone please provide sample test cases? m getting WA
--ans(Francky)--> You can build them on your own, with a python brute force for example, or even in C/C++ with very small moduli. No other test cases are provided. Good luck.

Last edit: 2014-11-03 13:55:41
[Lakshman]: 2014-07-14 11:09:19

@SHUBHAM JAIN try to solve some easy Fibonacci problem then come to this.
try FIBTWIST,FIBOSUM..

SHUBHAM JAIN: 2014-07-14 10:36:38

I am getting Segmentation fault runtime error in your compiler
but it is running properly in my compiler

[Lakshman]: 2014-06-25 10:59:50

@Francky My new solution seems to be fine for all corner cases, but still getting WA.
can you please give me some hint where my new solution fails.
Thanks.
--ans(Francky)--> There's a last corner. For two cases ,in my input file, your output is 0, but answer is not 0. Good luck, you're not so far.

Lakshman-->Thanks @Francky for this awesome problem. learned a lot from this.
--ans(Francky)--> As you can see in timings, you still have many secrets to be found for that kind of problems. The game is far from over. Good job, and thanks for your appreciation.
--Lakshman-->Actually my solution depends on some brute force while computing Pi**o. Thanks for the time limit. I will work on my faster algorithm and try to find out the bug in my faster algorithm.

--Lakshman-->Final optimization and its .21s

Last edit: 2014-07-14 15:34:43
[Lakshman]: 2014-03-02 22:30:37

@Francky can you please check my solution why I am getting runtime error.
Thanks
--ans(Francky)--> Your code is complex and not easy to read, I don't have more info by the judge. Good luck.

Last edit: 2014-03-02 23:43:14
fR0DDY: 2013-08-03 10:58:17

I am getting Runtime Error. Any hints for my solution or is my solution completely wrong?

[Lakshman]: 2013-05-12 07:06:57

Can you please give a bit hint where my solution fails .......
--ans--> You should try FRS2 first, your logic is wrong.

Last edit: 2013-05-12 07:39:52
(Tjandra Satria Gunawan)(曾毅昆): 2013-01-21 03:01:43

finally #1st place on this problem ;-)
--ans--> Good job, but the problem still keeps some secrets for a really serious boost...
EDIT: Thanks for the info, I have new idea, but only boost 0.08s.. for now my best is 0.22s..

Last edit: 2013-01-22 22:14:44
(Tjandra Satria Gunawan)(曾毅昆): 2012-09-05 18:20:13

I'm getting WA... any clues/hints?
--ans--> I didn't took a good look, but I can say now that you have some few good answers, so it could be a vicious overflow, if I have time I'll take a better look. It's yet a good job. Why don't you build a Python version to track those issues ?
Edit : you have some issues even with small input (n,m under 100, and k=2). You should test with a python brute force to find some "secrets", there's a lot to find.

RE: Thanks for your hints, Python brute-force really help me finding my mistake :-D

Last edit: 2012-09-06 02:56:03
nikoo28: 2012-09-02 18:19:14

those who got AC...can you please tell the output for
< snip >
--ans--> No other test case are provided, you have to build some on your own.

Last edit: 2012-09-02 18:29:28

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