#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

const ll MOD = 1e9+9;
const int MAX = 3333;
const int C[6] = {1, 5, 10, 50, 100, 500};
ll dp[6+1][MAX];

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

ll solve(ll M) {
    int q = M%500;
    vector<ll> c(6);
    for (int i = 0; i < 6; i++) {
        ll p = dp[6][q+i*500];
        ll q = 1;
        for (int j = 0; j < 6; j++) {
            if (i==j) continue;
            q *= i-j;
        }
        q = (q+MOD)%MOD;
        c[i] = p*mod_inverse(q, MOD);
        c[i] %= MOD;
    }
    ll m = M/500;
    m %= MOD;
    ll ret = 0;
    for (int i = 0; i < 6; i++) {
        ll tmp = 1;
        for (int j = 0; j < 6; j++) {
            if (i==j) continue;
            (tmp *= m-j) %= MOD;
        }
        ret += c[i]*tmp % MOD;
    }
    ret %= MOD;
    return (ret+MOD)%MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    dp[0][0] = 1;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < MAX; j++) dp[i+1][j] = dp[i][j];
        for (int j = 0; j < MAX-C[i]; j++) {
            (dp[i+1][j+C[i]] += dp[i+1][j]) %= MOD;
        }
    }
    int T;
    cin >> T;
    while (T--) {
        ll M;
        cin >> M;
        cout << solve(M) << endl;
    }
    return 0;
}