[BOJ] 15991 : 1, 2, 3 더하기 6

#include <cstdio>
const int m = 1e9+9;
int n, t, d[55555]={0,1,1,2,4};
int main() {
    for (int i = 5; i <= 55555; i++) {
        d[i] = ((long long)d[i-1]+d[i-2]+d[i-3]) % m;
    }
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        printf("%d\n", (d[n/2+1] + d[n/2]) % m);
    }
    return 0;
}