Https://www.interviewbit.com/problems/find-nth-fibonacci/


#1

what is wrong in this code? its showing error for A=1000

vector<vector<long long int > > multiply(vector<vector<long long int > > a,vector<vector<long long int > > b)
{
    int n=a.size();
    vector<vector<long long int > > ans(n,vector<long long int> (n,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        { 
            for(int k=0;k<n;k++)
            ans[i][j]+=a[i][k]*b[k][j];
        }
    }
    return ans;
}
vector<vector<long long int > > mp(vector<vector<long long int > > a,int A)
{
    if(A<=1)
    return a;
    vector<vector<long long int> > temp=mp(a,A/2);
    vector<vector<long long int> > ans = multiply(temp,temp);
    if(A%2==1)
    ans=multiply(ans,a);
    
    return ans;
}
int Solution::solve(int A) {
    if(A==0)
    return 0;
    if(A==1)
    return 1;
    vector<vector<long long int> > a={{1,1},{1,0}};
    vector<vector<long long int> > ans=mp(a,A-1);
    return ans[0][0]%(1000000007);


}