SPOJ.com - Problem FIBOSUM

FIBOSUM - Fibonacci Sum

The Fibonacci sequence is defined by the following relation:

F(0) = 0
F(1) = 1
F(N) = F(N - 1) + F(N - 2), N >= 2

Your task is very simple. Given two non-negative integers N and M, you have to calculate the sum (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.

Input

The first line contains an integer T (the number of test cases). Then, T lines follow. Each test case consists of a single line with two non-negative integers N and M.

Output

For each test case you have to output a single line containing the answer for the task.

Example

Input:
3
0 3
3 5
10 19

Output:
4
10
10857

Constraints

T <= 1000
0 <= N <= M <= 10⁹

Submit solution!

Added by:	David Gómez
Date:	2010-12-04
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	My Own

hide comments

2014-07-03 09:49:39 Archit Jain
nice problem

Last edit: 2014-07-03 09:49:53

2014-06-13 00:10:15 excursionist
nice problem....taught many things :o
Got ac in first attemp :)

2014-06-07 22:00:48 Sharprocks
Nice question
A single question taught 2 things :-)
Especially modular arithmetic :P

2014-05-19 06:41:42 saanc
can't believe that it is accepted in 1st go.. yepppeeeeeeeeeeeeeeee

2014-04-22 06:07:29 sarelfeniel
Great problem! I am content with 0.02 but I highly recommend reading the forum thread by Rafael Perrella. I guarantee you will learn something. Definitely never knew about that secret of the Fibonacci numbers.

@Francky, you have some awesome problems relating to Fibonacci and other series!
--ans(Francky)--> Thanks for your comment.

@Francky, no problem! My background in discrete mathematics is rather weak so it's nice to able to explore that area in more detail.

Last edit: 2014-04-23 07:52:02

2014-04-07 11:01:12 Francis
hi,all! I am stuck here and I need help! Thanks so much in advance.
I have tried both matrix exponentiation and Fast doubling methods to compute F(N) as referred in the comments below,but I just got TLE for this problem.I dont know how to get AC. It makes me crazy.
my code is here, http://ideone.com/mtHefP.
waiting for your replys!
--ans(Francky)--> Your methods are a bit slow for Python, use a faster language or improve your code, there's tons of idea for that, ... good luck.
@Francky Thx so much for your advice,Francky. Any specific ideas for improving the code??? I am a newbie for python and I have no idea of how to improve the code actually. :) waiting for your reply!
--ans(Francky)--> There's many other fib problems, most of them are harder, you will have TLE too. You should keep a fast language and try some speed experiments, after that you'll can try Python. I've started here with only Python, it was really hard to fight, but very instructive ; good luck.
@Francky oh,I think I see your point,Francky. Actually I meant to practise python by these probs. Now I will try C. Thx anyway! :)

@Francky hi,Francky. I finally pass it in C and Python. Many thx for your replys above.I still have questions for you.:)
The reason why the original python code always got TLE is that recursive function call consumes too much time I guess, although it is based on matrix exponentiation. I replace the recursive function call with while loop(code are at "snipped"). I got 4.4s,4.0M in python and 0.05s,1.6M in C. I am curious that how you got 0.00s,1.6M in C and 0.11s,4.0M in Python, that is very hard for me indeed. So I want to ask for your practical advice on how to make that(or how can I improve my code listed above), any advice about that is okay for me. I am really interested. Thx for your time of sharing truly. :) :) waiting for your replys!
--ans(Francky)--> The best key (but not the only one) is precomputation of some things : try to find what kind of data would be helpful very often, then compute them at start (a small amount of time, to be well thinking) and use them freely after to speed your computation. Try to keep a small code.
Now you have a 'fast' code, You can try speed experiment on <a href="http://www.spoj.com/problems/FLIB/">FLIB</a>, or Arya Rage ; I highly recommend them. You can check my <a href="http://www.spoj.com/problems/FRANCKY/">moto page</a>, I've set some Fibonacci tasks : you can try the easier ones, especially the challenge FIB64 where anyone can get points, or FRS2. Warning, I've set too some very hard problems. Good luck.

@Francky hi again,Francky. I have finished FLIB and Arya Rage referring to others ideas. Thx a lot for your recommendations :). I really learn a lot from that, like matrix exponentiation and precomputation(actually this is hard for me to decide how to precomputate rightly, and you seems so good at that :)). I will try to learn more and finish more probs and I will turn to you for help anytime I am stuck, :). Thx again! :)

Last edit: 2014-04-15 16:15:05

2013-11-11 23:39:41 Alexandre Henrique Afonso Campos
I have a solution that works for all listed cases here and in the forums previously mentioned here in the comments, including trick cases. Still getting WA.

Edit:
AC after considering the case that m>n but f(m)%1000000007 < f(n)%1000000007.

Last edit: 2013-11-11 23:49:45

2013-09-11 22:43:50 Rafael Perrella
I don't know any link where it is discussed. But you can start a thread and post the link here, then we can discuss it there.

@edit
I created the thread. You can easily find it in the forum.

Last edit: 2013-09-12 04:13:41