#include <iostream>
using namespace std;
int fib(int n);
int main()
{
int n;
cin>>n;
cout<<fib(n+2)%1000000009<<endl;
return 0;
}
int fib(int n)
{
if(n<=0)
return 0;
else if(n==1)
return 1;
else
return fib(n-1)+fib(n-2);
}//为什么TE了

@zcj: 这个递归是O(2^n)的，你可以用线性递推

for(int i=3;i<=n;i++) fib[i]=fib[i-1]+fib[i-2];