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
hide comments
rakcode1998:
2017-06-11 14:07:35
Why will it ever be negative? @sagnik_66
|
|
sagnik_66:
2017-06-09 18:23:45
Take care about the negative answers. Just add 1000000007.
|
|
anurag_333:
2017-05-30 13:19:40
@vineetpratik can you show me your dijkshra code??
|
|
thakur13:
2017-05-05 11:34:57
Jbardast Problem |
|
anurag_tangri:
2017-04-05 16:02:14
2 TLE 2 WA and finally AC:) |
|
rv404674:
2017-03-27 15:51:21
ac in 0.00 using fast matrix exponentiation |
|
vineetpratik:
2017-03-14 07:43:06
Dijkstra's fibonacci formula- 0.09sec 92M
|
|
vineetpratik:
2017-03-10 17:35:55
Dijkstra's fibonacci formula |
|
nilabja16180:
2017-03-04 09:09:01
Use long long, costed me one WA! |
|
priyasatbhaya:
2016-09-09 02:42:29
@baadshah_ thanks for the negative modulus 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 |