Getting wrong answer in 2 testcases, below is the code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 10000000007
ll k=2;
vector<vector> multiply(vector<vector> A,vector<vector> B)
{
vector<vector> C(k+1,vector(k+1));
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
for(int x=1;x<=k;x++)
{
C[i][j] = (C[i][j] + (A[i][x]*B[x][j])%mod)%mod;
}
}
}
return C;
}
vector<vector> pow(vector<vector> A,ll p)
{
if(p==1)
{
return A;
}
if(p&1)
{
return multiply(A,pow(A,p-1));
}
vector<vector> x = pow(A,p/2);
return multiply(x,x);
}
ll compute(ll n)
{
if(n==0 || n==1)
{
return 0;
}
if(n==2)
{
return 1;
}
vector<ll> f1(k+1);
f1[0]=0;
f1[1]=1;
vector<vector<ll>> T(k+1,vector<ll>(k+1));
T[1][1]=1;
T[1][2]=1;
T[2][1]=1;
T[2][2]=0;
T = pow(T,n-1);
ll res=0;
for(int i=1;i<=k;i++)
{
res = (res + (T[1][i]*f1[i])%mod)%mod;
}
return res;
}
int main()
{
ll t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<compute(n)<<endl;
}
return 0 ;
}