FIBO_USING_EXPONENTIATION

/***********************************FIBONACHI USING MATRIX EXPONENTIATION ******************/

##include<iostream>
using namespace std;
#include<bits/stdc++.h>

void matmult(long long int   a[][2],long long  int  b[][2],long long int  c[][2],long long int  M)//multiply matrix a and b. put result in c
{
    long long int i,j,k;
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            c[i][j]=0;
            for(k=0;k<2;k++)
            {
                c[i][j]+=(a[i][k]*b[k][j]);
                c[i][j]=c[i][j]%M;
            }
        }
    }
 
}
void matpow(long long int Z[][2],long long int n,long long int  ans[][2],long long M)
//find ( Z^n )% M and return result in ans
{
 
    long long int temp[2][2];
    //assign ans= the identity matrix
    ans[0][0]=1;
    ans[1][0]=0;
    ans[0][1]=0;
    ans[1][1]=1;
    long long int i,j;
    while(n>0)
    {
        if(n&1)
        {
            matmult(ans,Z,temp,M); // z*arr aand storing in ans 
            for(i=0;i<2;i++)
                for(j=0;j<2;j++)
                    ans[i][j]=temp[i][j];
        }
        matmult(Z,Z,temp,M);//   z*z increasing power of z 
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
                Z[i][j]=temp[i][j];
 
 
        n=n/2;
    }
    return;
     
}

long long int findFibonacci(long long int n,long long int M)
{
     
    long long int  fib;
    if(n>2)
    {
        long long int Z[2][2]={{1,1},{1,0}},result[2][2];//modify matrix a[][] for other recurrence relations
        matpow(Z,n-2,result,M);
        fib=result[0][0]*1 + result[0][1]*0;    //final multiplication of Z^(n-2) with the initial terms of the series
    }
    else
        fib=n-1;
         
    return fib;

}
 int main()
   {
    long long int n,m;
      while(scanf("%lld %lld",&n,&m)==2)
      {
       
      
      long long int kk=1;
      
       for(int i=0;i<m;i++) kk*=2;
        //cout<<kk<<endl;
     long long int ll=findFibonacci(n+1,kk);
      cout<<ll<<endl;
   }
   return 0;
   }

NOTE ---- NOTE FOR MATRIX MUMTIPLICAION PART WE CAN ALSO DECREASE TIME BY USING STRASSION ALGO 

OF  FORE RUSHION ALGO FOR BINARY MATRIX