Given f(1)=1 , f(2)=1 , and f(n) = 100*f(n-1)+200f(n-2) .

Now , i have to calculate f(n) rof n upto 10^9 , so obvious approach id to use matrix exponentiation …

I came up with this logic , but it gives wrong output . Can you please explain the reason ?

It fails with n=3 , but i am not able to come up with how to resolve it .

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll m=1000000007;
ll x,y,z,w;
void ml(ll F[2][2],ll M[2][2])
{
x = ((F[0][0]%m)*(M[0][0]%m))%m + ((F[0][1]%m)*(M[1][0]%m))%m;
y = ((F[0][0]%m)*(M[0][1]%m))%m + ((F[0][1]%m)*(M[1][1]%m))%m;
z = ((F[1][0]%m)*(M[0][0]%m))%m + ((F[1][1]%m)*(M[1][0]%m))%m;
w = ((F[1][0]%m)*(M[0][1]%m))%m + ((F[1][1]%m)*(M[1][1]%m))%m;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
//cout<<F[0][0]<<" " <<F[0][1]<<" "<< F[1][0]<<" " <<F[1][1]<<endl;
}
void po(ll F[2][2],ll n)
{
if( n<=1)
return;
ll M[2][2] = {{100,200},{1,0}};
po(F,n/2);
ml(F,F);
if( n%2 != 0 )
ml(F,M);
}
ll f(ll n)
{
ll F[2][2] = {{100,200},{1,0}};
if(n<=2)
return 1;
po(F,n-1);
return F[0][0];
}
int main(){
freopen("input.txt", "rt", stdin);
ll ans,n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%llu",&n);
ans=f(n);
printf("%llu\n",ans);
}
return 0;
}
```