Hi Everyone,
Can anyone please help me in finding out the nth term for fibonacci sequence when N is very large.
I have tried the below approach,but I'm not able to find exact solution.

#include "iostream"
using namespace std;
typedef long long int ll;
// Function to compute F raise to power n-2.

void multiply(ll a[3][3], ll b[3][3])
{
// Creating an auxiliary matrix to store elements
// of the multiplication matrix
ll mul[3][3];
for (ll i = 0; i < 3; i++)
{
for (ll j = 0; j < 3; j++)
{
mul[i][j] = 0;
for (ll k = 0; k < 3; k++)
mul[i][j] += a[i][k]*b[k][j];
}
}

// storing the multiplication result in a[][] 
for (ll i=0; i<3; i++) 
    for (ll j=0; j<3; j++) 
        a[i][j] = mul[i][j];  // Updating our matrix 

}
ll power(ll F[3][3], ll n)
{
ll M[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}};

// Multiply it with initial values i.e with 
// F(0) = 0, F(1) = 1, F(2) = 1 
if (n==1) 
    return F[0][0] + F[0][1]; 

power(F, n/2); 

multiply(F, F); 

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

// Multiply it with initial values i.e with 
// F(0) = 0, F(1) = 1, F(2) = 1 
return F[0][0] + F[0][1] ; 

}

// Return n'th term of a series defined using below
// recurrence relation.
// f(n) is defined as
// f(n) = f(n-1) + f(n-2) + f(n-3), n>=3
// Base Cases :
// f(0) = 0, f(1) = 1, f(2) = 1
ll findNthTerm(ll n)
{

ll F[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}} ; 

//Base cases 
if(n==0) 
    return 0; 
if(n==1 || n==2) 
    return 1; 

return power(F, n-2); 

}
int main()
{
ll n = 49;

cout << findNthTerm(n);

return 0;
}

My ouptput for N=49->3122171529233

F40 102334155
F41 165580141
F42 267914296
F43 433494437
F44 701408733
F45 1134903170
F46 1836311903
F47 2971215073
F48 4807526976
F49 7778742049

Thanks