Fibonacci Sums

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define MAXN 100000
#define MOD 10009
using namespace std;

int main() {
    int t, x, y, fib[MAXN+1];
    scanf ("%d", &t);
    while (t--) {
        int r=0;
        bool done=false;
        scanf ("%d %d", &x, &y);
        fib[0]=0;
        fib[1]=1;
        if (!done) {
            for (int k=2; k<=MAXN; k++) {
                fib[k]=fib[k-1]+fib[k-2];
            }
            done=true;
        }
        for (int j=x; j<=y; j++) {
            r += fib[j];
        }
        printf("%d\n", r%MOD);
    }
    return 0;
}