#include <cstdio>

typedef long long ll;

const ll MOD = 1e9 + 9;

int T;
ll M;

// dp2[i][j] := 和がjとなるような2未満の整数i個の組の数
ll dp2[30][30], dp5[30][30];
ll perm_inv[7];

ll expt(ll a, ll n){
    ll res = 1ll;
    while(n > 0){
        if(n & 1){res = res * a % MOD;}
        n >>= 1;
        a = a * a % MOD;
    }
    return res;
}

ll nCk(ll n, ll k){
    if(n < 0 || k < 0 || n < k){return 0ll;}

    ll res = 1ll;
    for(ll i=n;i>n-k;i--){
        res = i % MOD * res % MOD;
    }

    return res * perm_inv[k] % MOD;
}

ll nHk(ll n, ll k){
    if(n == 0 && k == 0){return 1ll;}
    return nCk(n+k-1, k);
}

ll solve(){
    ll res = 0ll;

    int i1 = M % 5;
    for(int i5=(M-i1)%10/5;i5<4;i5+=2){ // 5 (2)
        for(int i10=(M-i1-i5*5)%50/10;i10<15;i10+=5){ // 10 (5)
            for(int i50=(M-i1-i5*5-i10*10)%100/50;i50<8;i50+=2){ // 50 (2)
                for(int i100=(M-i1-i5*5-i10*10-i50*50)%500/100;i100<25;i100+=5){ // 100 (5)
                    ll diff = M - (1ll * i1 + i5 * 5 + i10 * 10 + i50 * 50 + i100 * 100);
                    res = (res + dp5[1][i1] * dp2[2][i5] % MOD * dp5[3][i10] % MOD * dp2[4][i50] % MOD * dp5[5][i100] % MOD * nHk(diff/500+1, 5) % MOD) % MOD;               
                }
            }
        }
    }

    return res;
}

int main(){
    perm_inv[0] = 1;
    for(int i=1;i<=6;i++){
        perm_inv[i] = perm_inv[i-1] * expt(i, MOD-2) % MOD;
    }
    
    dp2[0][0] = 1ll;
    for(int i=1;i<30;i++){
        for(int j=0;j<30;j++){
            for(int k=0;k<2;k++){
                if(j-k < 0){continue;}
                dp2[i][j] = (dp2[i][j] + dp2[i-1][j-k]) % MOD;
            }
        }
    }
    
    dp5[0][0] = 1ll;
    for(int i=1;i<30;i++){
        for(int j=0;j<30;j++){
            for(int k=0;k<5;k++){
                if(j-k < 0){continue;}
                dp5[i][j] = (dp5[i][j] + dp5[i-1][j-k]) % MOD;
            }
        }
    }
    
    scanf("%d", &T);

    for(int i=0;i<T;i++){
        scanf("%lld", &M);

        printf("%lld\n", solve());
    }
}