Fibonacci Sum

#include <stdio.h>

#define MAX 100005
#define mod 1000000009
int data[MAX];

void generate(){
    for(int i=2;i<MAX;i++){
        data[i] = data[i-2]%mod + data[i-1]%mod;
    }
}

int main(){
    int tc, temp;
    data[0] = 0;
    data[1] = 1;
    generate();
    scanf("%d", &tc);
    for(int i=1;i<=tc;i++){
        scanf("%d", &temp);
        printf("Case #%d: %d\n", i, (data[temp+2]-1)%mod);
    }
    return 0;
}