斐波那契数列的定义如下：

 

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的结果即可。

 

 

 

输入

输入1个数n(1 <= n <= 10^18)。

输出

输出F(n) % 1000000009的结果。

输入样例

11

输出样例

89 。 代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define mod 1000000009using namespace std;void mul(long long (*a)[2],long long (*b)[2]) {    long long d[2][2] = {
    0};    for(int i = 0;i < 2;i ++) {        for(int j = 0;j < 2;j ++) {            for(int k = 0;k < 2;k ++) {                d[i][j] += (a[i][k] * b[k][j]) % mod;            }            d[i][j] %= mod;        }    }    for(int i = 0;i < 2;i ++) {        for(int j = 0;j < 2;j ++) {            a[i][j] = d[i][j];        }    }}int f(long long n) {    long long a[2][2] = {
    1,1,1,0},d[2][2] = {
    1,0,0,1};    while(n) {        if(n % 2)mul(d,a);        n /= 2;        mul(a,a);    }    return d[1][0];}int main() {    long long n;    cin>>n;    cout<