For this Question: Chapo is the most exotic thing ever. Sid wants to give Chapo to the person who solves this little tricky question on Fibonacci numbers.
Fib(i) refers to i-th Fibonacci Number. First few Fibonacci numbers are Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2 ...
Given k=331.
Also, F(N) = (sum of Fib(i*k) where i varies from 0 to N-1).
You will be given two positive integers, m and n. You need to find the value of  F(m**n)%1000000009. Here, m**n means m raised to the power n. 

Can you get a chapo?The first and the only line of input contains 2 integers m and n.


Constraints
1 <= m, n <= 1000000000Print a single integer, the value of F(m**n)%1000000009.Sample Input 1
2 1

Sample Output 1
242667188

Sample Input 2
100 100

Sample Output 2
822562876

Explanation for Sample 1:
F(2**1)%1000000009 = F(2)%1000000009 = (Fib(0)+Fib(331))%1000000009 = 242667188.

Note: In 2nd test case, there will be 100**100 terms., I have written this Solution Code: #include <bits/stdc++.h>

#define int long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define all(a) (a).begin(),(a).end()
#define x first
#define y second
#define sz(x) (int)x.size()
#define endl '\n'
#define hell 1000000009
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
class matrix{
public:
int n;
vector<vi> val;
matrix(int n=2);
matrix operator+(const matrix&) const;
matrix operator-(const matrix&) const;
matrix operator*(const matrix&) const;
matrix& operator=(const matrix& b){
val=b.val;
n=b.n;
return *this;
}
void set(int x){
rep(i,0,n){
rep(j,0,n){
val[i][j]=x;
}
}
}
void print(){
rep(i,0,n){
rep(j,0,n){
cout<<val[i][j]<<" ";
}
cout<<endl;
}
}
matrix mul(int a){
matrix ans(this->n);
rep(i,0,this->n){
rep(j,0,this->n){
ans.val[i][j]=a*this->val[i][j]%hell;
}
}
return ans;
}
};
matrix::matrix(int x){
n=x;
val.resize(x);
rep(i,0,x){
val[i].resize(x);
}
}
matrix matrix::operator+(const matrix& b) const{
matrix ans(b.n);
rep(i,0,b.n){
rep(j,0,b.n){
ans.val[i][j]=this->val[i][j]+b.val[i][j];
}
}
return ans;
}
matrix matrix::operator-(const matrix& b) const{
matrix ans(b.n);
rep(i,0,b.n){
rep(j,0,b.n){
ans.val[i][j]=this->val[i][j]-b.val[i][j];
}
}
return ans;
}
matrix matrix::operator*(const matrix& b) const{
matrix ans(b.n);
rep(i,0,b.n){
rep(j,0,b.n){
rep(k,0,b.n){
ans.val[i][j]+=this->val[i][k]*b.val[k][j];
ans.val[i][j]%=hell;
}
}
}
return ans;
}
matrix identity(int N=2){
matrix ans(N);
rep(i,0,N){
ans.val[i][i]=1;
}
return ans;
}
matrix matexpo(matrix a, int n){
if(n==0){
return identity(a.n);
}
if(n==1) return a;
matrix x=matexpo(a,n/2);
matrix r=x*x;
if(n&1) r=r*a;
return r;
}
matrix GP(matrix A,matrix R,int N){
matrix T(2*R.n),B=A;
rep(i,0,2*R.n){
rep(j,0,2*R.n){
if(i<R.n and j<R.n){
T.val[i][j]=R.val[i][j];
}
else if(i<R.n){
T.val[i][j]=(i==j-R.n);
}
else if(j>=R.n){
T.val[i][j]=(i==j);
}
}
}
T=matexpo(T,N);
rep(i,0,A.n){
rep(j,0,A.n){
B.val[i][j]=T.val[i][j+A.n];
}
}

return B*A;
}
int expo(int base,int exponent,int mod){
int ans=1;
while(exponent!=0){
if(exponent&1) ans=(1LL*ans*base)%mod;
base=(1LL*base*base)%mod;
exponent>>=1;
}
return ans%mod;
}
void solve(){
int m,n,k=331;
cin>>m>>n;
int p=(expo(m,n,hell-1)-1+hell-1)%(hell-1);
matrix mat(2);
mat.val[0][0]=mat.val[0][1]=mat.val[1][0]=1;
mat.val[1][1]=0;
matrix a=matexpo(mat,k-1);
matrix r=matexpo(mat,k);
matrix res=GP(a,r,p);
cout<<res.val[0][0]<<endl;
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}, In this Programming Language: C++, Now tell me if this Code is compilable or not?