题目传送门
代码：
#include<bits/stdc++.h>
using namespace std;#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ls (rt<<1)
#define rs (rt<<1|1)
#define pb push_back
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define MEM(a,b,start,end) for(int ii=start;ii<=end;ii++) a[ii]=b
#define low(x) (x&(-x))
#define v(x) vector<x>
#define Map1(a,b) map<a,b>
#define Map2(a,b) unordered_map<a,b>
#define pqg(x) priority_queue<x,vector<x>,greater<x> >
#define pql(x) priority_queue<x,vector<x>,less<x> >
typedef unsigned long long ULL;
typedef long long LL;
typedef double D;
typedef complex<double> COMD;
const int maxn=100000+100;
const LL mod=1e9+9;LL T[2][2]={
{1,1},{1,0}},tmp[2][2];;
LL ans[2];void mymul(LL A[][2],LL B[][2]){LL mul[2][2];memset(mul,0,sizeof(mul));for(int i=0;i<2;i++){for(int j=0;j<2;j++){for(int t=0;t<2;t++){mul[i][j]=(mul[i][j]+A[i][t]*B[t][j]%mod)%mod;}}} for(int i=0;i<2;i++) for(int j=0;j<2;j++) A[i][j]=mul[i][j];
}void mypow(LL n){tmp[0][0]=tmp[1][1]=1;tmp[0][1]=tmp[1][0]=0;while(n){if(n&1) mymul(tmp,T);mymul(T,T);n>>=1;}
}int main(){LL n;scanf("%lld",&n);mypow(n);printf("%lld\n",tmp[0][1]);
}