# Fibonacci problem, exceeding the maximum value of int

I m trying to solve https://www.spoj.com/problems/FIBOSUM/ problem.

``````MOD = 1000000007;

function copy(a, b) {
a[0][0] = b[0][0];
a[0][1] = b[0][1];
a[1][0] = b[1][0];
a[1][1] = b[1][1];
}

function multiply(fib, base) {
let mat = [[], []];
copy(mat, fib);

mat[0][0] = (fib[0][0]*base[0][0] + fib[0][1]*base[1][0]) % MOD;
mat[0][1] = (fib[1][0]*base[0][0] + fib[1][1]*base[1][0]) % MOD;
mat[1][0] = (fib[0][0]*base[0][1] + fib[0][1]*base[1][1]) % MOD;
mat[1][1] = (fib[1][0]*base[0][1] + fib[1][1]*base[1][1]) % MOD;
copy(fib, mat);
}

function calcMatrix(fib, n) {
const base = [[1,1], [1,0]];
fib[0][0] = 1;
fib[0][1] = 0;
fib[1][0] = 0;
fib[1][1] = 1;

while (n) {
print(n);
if (n&1) {
multiply(fib, base);
}
multiply(base, base);
print('bef', n)
n = n.toString(2).slice(0, -1); //same as n = n >> 1;
print('aft', n)
}
}

while(t--)
{
N = Number(N);
M = Number(M);
let fib = [[],[]];
calcMatrix(fib, N);
let fn = fib[0][1];
let fn1 = fib[1][1] ;

calcMatrix(fib, M-N+2);
// (a%mod -b%mod +mod)%mod
let sum =  ((fib[0][0]-1)*fn + (fib[0][1]-1)*fn1 + MOD) % MOD;
print('wyni', sum);
}
``````

There is my solution https://ideone.com/25HLU7. For n = 78 the result is correct, higher values make result exceeding max int. I can t use BigInt(), because of spidermonkey.