# Error while implementing matrix exponentiation

I tried to implement fast exponentiation using explanation from article on geeksforgeeks but it shows error while solving: https://www.spoj.com/problems/FIBOSUM/

Can anyone explain whatâ€™s wrong with the code? I tried by computing Fibonacci sum for last element of given range and Fibonacci sum of element before beginning of range and subtracted them, but it shows tle and incorrect answer.

``````import java.util.*;
import java.io.*;

class GFG {

public static int fib(int n) {
if(n<=1)
return n;
int f[][] = new int[][]{{1,1},{1,0}};
int g = power(f,n-1);
return g;

}

public static int power(int f[][],int n){
int b[][] = new int[][]{{1,1},{1,0}};
int sum = 1;
for(int i = 2;i<=n;i++){
multiply(f,b);
sum = sum+f[0][0];
}
return((sum+1)%1000000007);
}

public static void multiply(int f[][],int b[][]){
int x = f[0][0]*b[0][0]+f[0][1]*b[1][0];
int y = f[0][0]*b[0][1]+f[0][1]*b[1][1];
int z = f[1][0]*b[0][0]+f[1][1]*b[1][0];
int w = f[1][0]*b[0][1]+f[1][1]*b[1][1];
f[0][0] = x;
f[0][1] = y;
f[1][0] = z;
f[1][1] = w;

}
public static void main (String[] args) throws Exception {
Scanner s = new Scanner(System.in);
int t = s.nextInt();
for(int i = 1;i<=t;i++){
int n = s.nextInt();
int m = s.nextInt();
if(n!=0)
n = fib(n-1);
m = fib(m);
System.out.println((m-n)%1000000007);

}
}
}
``````