#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
typedef long long ll;

const ll mod = 1e9 + 9;
vector<ll> d[500];

long long modpow(long long a, long long b, long long mod) {
	long long ret = 1;
	for (; b > 0; a = a * a % mod, b /= 2) if (b & 1) ret = ret * a % mod;
	return ret;
}

long long modinv(long long a, long long mod) {
	return modpow(a, mod - 2, mod);
}

template<class T> ostream &operator <<(ostream &os, const vector<T> &v) { for (T x : v) os << x << " "; return os; }

void precalc() {
	// dp[i][j] := i番目までの硬貨を使ってj円支払う場合の数
	const int N = 5000;
	static ll dp[7][N];
	
	int a[] = { 1, 5, 10, 50, 100, 500 };
	dp[0][0] = 1;
	rep(i, 6) rep(j, N) {
		dp[i + 1][j] = dp[i][j];
		if (j - a[i] >= 0) (dp[i + 1][j] += dp[i + 1][j - a[i]]) %= mod;
	}

	rep(i, 5000) d[i % 500].push_back(dp[6][i]);
}

ll interpolate(ll x, ll y) {
	x %= mod;
	ll ret = 0;
	int n = d[y].size();
	rep(i, n) {
		ll v = d[y][i];
		rep(j, n) if (i != j) {
			(v *= x - j) %= mod;
			(v *= modinv(i - j, mod)) %= mod;
		}
		(ret += v) %= mod;
	}
	if (ret < 0) ret += mod;
	return ret;
}

int main() {
	precalc();
	int t;
	cin >> t;
	rep(i, t) {
		ll m;
		cin >> m;
		cout << interpolate(m / 500, m % 500) << endl;
	}
	return 0;
}