# Fastest Way to calculate Nth fibonacci number modulo M

Hello frendz …

code is updated and syncronized so that you can get AC on spoj with it … it is able to answer 61100 test cases on a rough idea. We can do some optimisation and can take it to 62000 easily . suggest some optimisation … i have one in my mind …

@i_am_what_i_am
you can try it now …

Hey guys i have applied the optimisation and boom i am able to take it to 63450 from 61100 . Think of some more optimisations .

@i_am_what_i_am
he was actually correct that this is not the fastest code for generating the answer but this may be the simplest code .

1 Like

could anyone explain what is the logic behind the function long long int f(long long int n, int depth=0) and
long long int mulmod(long long int a, long long int b) . Thankyou in advance.

```https://www.codechef.com/problems/CURR3
#include
using namespace std;
#define ll long long
#define m 1000000007
void multiply(ll f[][2],ll g[][2])
{
ll a=(f[0][0]*g[0][0]+f[0][1]*g[1][0])%m;
ll b=(f[0][0]*g[0][1]+f[0][1]*g[1][1])%m;
ll c=(f[1][0]*g[0][0]+f[1][1]*g[1][0])%m;
ll d=(f[1][0]*g[0][1]+f[1][1]*g[1][1])%m;

f[0][0]=a;
f[0][1]=b;
f[1][0]=c;
f[1][1]=d;
}
void power(ll f[2][2],ll n)
{
ll g[2][2]={{1,1},{1,0}};
if(n==0||n==1)
return;
power(f,n/2);
multiply(f,f);

if(n%2==1)
multiply(f,g);
}
ll fib(ll n)
{
ll f[2][2]={{1,1},{1,0}};
if(n==0)
return 0;
power(f,n-1);
return f[0][0]%m;
}

int main() {
ll n;
cin>>n;
cout<<fib(n)%m;
}```
//