# include

``````# include <math.h>
using namespace std;

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0]%1000000007;
}

void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

if (n%2 != 0)
multiply(F, M);
}

void multiply(int F[2][2], int M[2][2])
{
int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

int main()
{long long i,n,x,sum=0,t=0;
cin>>i;

while(i--)
{
cin>>n>>x;
sum=(fib(n-1)*pow(x,n+2))+((fib(n)*pow(x,n+1))-x);
t=(x*x)+x-1;
cout<<(((sum/t)%1000000007)%1000000007)<<endl;

}
}``````

This is just at a glance, but you’re not performing the calculations under modulo inside the `multiply` function.

1 Like

constraints are:

1 ≤ T ≤ 1000

0 ≤ n ≤ 10^15

0 ≤ x ≤ 10^15

use long long instead of int,

Reference solution, please explain the approach you are applying to solve this problem.

//