#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))

const int MOD = (int)(1e9+9);
const int coins[] = {5,10,50,100,500};

ll dp[1000001];

ll extgcd(ll a,ll b,ll &m,ll &n){ll g=a;m=1;n=0;if(b)g=extgcd(b,a%b,n,m),n-=(a/b)*m;return g;}

ll divmod(ll n, ll m, ll mod){
    ll a,b;
    extgcd((m+mod)%mod,mod,a,b);
    return (n * a) % mod;
}

template<class _T>
_T Lagrange(const vector<pair<_T,_T> > &fj, _T x, ll mod = 0){
    int n = fj.size();
    _T res = 0;
    for(int j = 0; j < n; j++){
        _T ljx = 1;
        for(int k = 0; k < n; k++){
            if(j == k) continue;
            if(!mod) ljx *= (x - fj[k].first);
            else ljx = (ljx * ((x - fj[k].first) % mod)) % mod;
        }
        for(int k = 0; k < n; k++){
            if(j == k) continue;
            if(!mod) ljx /= (fj[j].first - fj[k].first);
            else ljx = divmod(ljx, fj[j].first - fj[k].first, mod);
        }
        res += fj[j].second * ljx; res %= mod;
    }
    if(mod) res = (res + mod) % mod;
    return res;
}

int main(){
    REP(i,1000001) dp[i] = 1;
    REP(i,5) REP(j,1000001){
        int k = j-coins[i];
        if(k >= 0) dp[j] = (dp[j] + dp[k]) % MOD;
    }

    int T; cin >> T;
    REP(i,T){
        ll M; cin >> M;
        ll x = M / 500, r = M % 500;
        vector<pair<ll,ll> > v;
        REP(i,6) v.push_back(make_pair(i, dp[i*500+r]));
        cout << Lagrange<ll>(v, x, MOD) << endl;
    }
}