| Submit | All submissions | Best solutions | Back to list |
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 <= 109
| 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
|
||||||||||||||
|
2016-08-16 22:19:13
In case of a doubt, check out the resources mentioned here : <snip> Last edit: 2023-01-31 21:44:54 |
||||||||||||||
|
2016-07-31 07:26:43 swap
Learnt a lot! @baadshah_ thanks! It took me some time to understand about negative modulus! |
||||||||||||||
|
2016-07-17 20:48:07
Oh god the mod..! Cost me 9 WAs! You don't have to apply mod to just the answer. You have to apply mod to the matrix at each single step(each time you multiply matrices)!! No idea why even after using long long int!! |
||||||||||||||
|
2016-07-15 20:57:01
if u get negative ans just add 1000000007 to the ans!! |
||||||||||||||
|
2016-06-11 22:40:31 harsh gupta
can anyone post a tricky test case which involves negative modulo ?? |
||||||||||||||
|
2016-05-24 11:50:04
Used Dijkstra's formula...with memorization... F(2*n-1)=F(n)*F(n)+F(n-1)*F(n-1) F(2*n)=(2*F(n-1)+F(n))*F(n).. 0.02 secs..AC |
||||||||||||||
|
2016-05-21 16:25:12
I mistakingly printed 1 for 0 0 case . -_- . costed me 3 WA!! |
||||||||||||||
|
2016-05-13 11:02:39 SUBHAM SANGHAI
@buttman , Though given n<=m .But you are taking mod with 10^9+7;So there might be a problem of a negative mod.Take this case ,suppose (N!)=(10^9+6) and (M)!=(10^9)+8, (M!)%mod=1 and (N!)%mod=(10^9)+6; so here (M!)-(N!) <0 Last edit: 2016-05-13 11:05:05 |
||||||||||||||
|
2016-03-15 18:24:39
Interesting Problem Learnt lot of new concepts and specially properties of Fibonacci Series |
||||||||||||||
|
2016-02-26 12:45:54 Vmcode
@ abhi_vicky, thanks, got A.C 0.0 |
||||||||||||||
RSS