本来应该60pts啊

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[114514] = {0,1,1};
ll maxn = 1000000009;
int main(){
    ll n;
    scanf("%lld",&n);

    for (int l = 3; l <= 99;l++){
        f[l] = f[l-1] + f[l-2];
    }

    printf("%lld",f[n] % maxn);
    return 0;
}