Fibonacci Problem :Calculate the sum (F(X) + F(X + 1) + ... + F(Y)) mod 1000000007, where F(N)=F(N-1)+F(N-2),N>=2

Interview question asked in OYO Rooms company.

You are given two non-negative integers X and Y, you have to calculate the sum
(F(X) + F(X + 1) + ... + F(Y)) mod 1000000007, where F(N)=F(N-1)+F(N-2),N>=2.

Input

The two non-negative integers X and Y.

Output

For each test case you have to output a single line containing the answer.
Since the answer can be huge i.e go out of the bounds of integers, You are required to print the answer MOD 10^9+7

Example

Input:

2 6

Output:

19

Explanation

The fibonacci series is like this  0 ,1, 1, 2, 3, 5, 8, 13, 21,....

For the test case, we need to calculate the sum of the Fibonacci series from its 2nd term till 6th. ( i.e 1 + 2 + 3 + 5 + 8 ) = 19%(10^9+7) = 19

import java.math.BigInteger;  
 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.Scanner;  
 /**  
  *   
  */  
 /**  
  * @author Dixit  
  *   
  */  
 public class FibonacciProblem {  
      /**  
       * @param args  
       */  
      public static void main(String a[]) {  
           int mod = 1000000007;  
           Scanner sc = new Scanner(System.in);  
           int x = sc.nextInt();  
           int y = sc.nextInt();  
           List<Integer> list = new ArrayList<Integer>();  
           list = getFibo(y);  
           if (!list.isEmpty()) {  
                int sum = 0;  
                BigInteger result = BigInteger.valueOf(0);  
                for (int j = x; j <= y; j++) {  
                     sum = sum + list.get(j);  
                }  
                result = BigInteger.valueOf(sum % mod);  
                System.out.println("Result:" + result);  
           }  
      }  
      private static List<Integer> getFibo(int y) {  
           // TODO Auto-generated method stub  
           List<Integer> l = new ArrayList<Integer>();  
           int a = 0;  
           int b = 1;  
           if (y == 0) {  
                return l;  
           }  
           if (y == 1) {  
                l.add(a);  
                l.add(b);  
                return l;  
           } else {  
                l.add(a);  
                l.add(b);  
                for (int i = 2; i <= y; i++) {  
                     int sum = a + b;  
                     a = b;  
                     b = sum;  
                     l.add(sum);  
                }  
           }  
           return l;  
      }  
 }  

 Output  
 2  
 6  
 Result:19  

Enjoy Programming