fork download
copy 
  1. MOD = 1000000007;
  2.  
  3. function copy(a, b) {
  4. 	a[0][0] = b[0][0];
  5. 	a[0][1] = b[0][1];
  6. 	a[1][0] = b[1][0];
  7. 	a[1][1] = b[1][1];
  8. }
  9.  
  10. function multiply(fib, base) {
  11. 	let mat = [[], []];
  12. 	copy(mat, fib);
  13.  
  14. 	mat[0][0] = (fib[0][0]*base[0][0] + fib[0][1]*base[1][0]) % MOD;
  15.     mat[0][1] = (fib[1][0]*base[0][0] + fib[1][1]*base[1][0]) % MOD;
  16.     mat[1][0] = (fib[0][0]*base[0][1] + fib[0][1]*base[1][1]) % MOD;
  17.     mat[1][1] = (fib[1][0]*base[0][1] + fib[1][1]*base[1][1]) % MOD;
  18.     copy(fib, mat);
  19. }
  20.  
  21. function calcMatrix(fib, n) {
  22. 	const base = [[1,1], [1,0]];
  23. 	fib[0][0] = 1;
  24. 	fib[0][1] = 0;
  25. 	fib[1][0] = 0;
  26. 	fib[1][1] = 1;
  27.  
  28. 	while (n) {
  29. 		if (n&1) {
  30. 			multiply(fib, base);
  31. 		}
  32. 		multiply(base, base);
  33. 		n = n.toString(2).slice(0, -1);
  34. 	}
  35. }
  36.  
  37. let t = parseInt(readline());
  38. while(t--)
  39. {
  40.     [N, M] = readline().split(' ');
  41.     N = Number(N);
  42.     M = Number(M);
  43.     let fib = [[],[]];
  44.     calcMatrix(fib, N);
  45.     let fn = fib[0][1];
  46.     let fn1 = fib[1][1] ;
  47.  
  48.     calcMatrix(fib, M-N+2);
  49.     let sum =  ((fib[0][0]-1)*fn % MOD + (fib[0][1]-1)*fn1 % MOD + MOD) % MOD;
  50.     print(sum);
  51. }
Success #stdin #stdout 0.04s 17052KB
comments (?)
stdin
copy 
5
0 3
3 5
10 19
78 78
107 107
stdout
copy 
4
10
10857
261180706
672614545
https://ideone.com/25HLU7
language:
JavaScript (SMonkey 60.2.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!