EvenF

 1 #pragma GCC optimize(3)
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const ll mod=1e9+9;
 6 const int maxn=1e6+50;
 7 struct Mat
 8 {
 9     int n,m;
10     ll mat[2][2];
11     Mat(){
12         memset(mat,0,sizeof(mat));
13         n=2,m=2;
14     }
15     Mat(int x,int y){
16         memset(mat,0,sizeof(mat));
17         n=x,m=y;
18     }
19     Mat operator*(Mat b){
20         Mat c(n,b.m);
21         for(int i=0;i<n;i++)
22             for(int j=0;j<b.m;j++)
23                 for(int k=0;k<m;k++){
24                     c.mat[i][j]=(c.mat[i][j]+mat[i][k]*b.mat[k][j]%mod)%mod;
25                 }
26         return c;
27     }
28 }E,A;
29 Mat qpow(Mat a,ll b)
30 {
31     Mat res=E;
32     while(b){
33         if(b&1) res=res*a;
34         a=a*a;
35         b>>=1;
36     }
37     return res;
38 }
39 char str[maxn];
40 int n;
41 int main()
42 {
43     A.n=A.m=2;
44     A.mat[0][0]=2;A.mat[0][1]=1;
45     A.mat[1][0]=1;A.mat[1][1]=1;
46     scanf("%s",str+1);
47     n=strlen(str+1);
48     if(n==1 && str[1]==‘0‘){
49         printf("1\n");
50         return 0;
51     }
52     for(int i=n;i>=1;i--){
53         if(str[i]>=‘1‘){
54             str[i]--;
55             break;
56         }
57         else str[i]=‘9‘;
58     }
59     E.n=E.m=2;
60     E.mat[0][0]=1;E.mat[0][1]=0;
61     E.mat[1][0]=0;E.mat[1][1]=1;
62     Mat ans=E;
63     for(int i=1;i<=n;i++){
64         int tag=str[i]-‘0‘;
65         ans=qpow(ans,10)*qpow(A,tag);
66     }
67     printf("%lld\n",(ans.mat[0][0]+ans.mat[0][1])%mod);
68     return 0;
69 }