斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)
给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。
Input输入1个数n(1 <= n <= 10^18)。Output输出F(n) % 1000000009的结果。Sample Input
11Sample Output
89
#include<iostream>
#include<algorithm>
using namespace std;
const long long INF=1000000009;
struct Node{long long M[2][2];
}t;
Node Mult(Node p,Node q)
{Node x={0};for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++){x.M[i][j]+=(p.M[i][k]*q.M[k][j])%INF;x.M[i][j]%=INF;}return x;
}
Node power(long long n)
{Node ans=t;if(n<0) return ans;while(n){if(n&1){ans=Mult(ans,t);n--;}t=Mult(t,t);n>>=1;}return ans;}
int main()
{long long n;scanf("%lld",&n);t.M[0][0]=1;t.M[0][1]=1;t.M[1][0]=1;t.M[1][1]=0;Node temp=power(n-2);printf("%lld",temp.M[0][0]);
}