#include <iostream>

using namespace std;

const long long MOD = 1000000009;
const int MAX = 5000;
const long long COIN[] = {1, 5, 10, 50, 100, 500};

int T;
long long M;
long long dp[MAX];

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

long long mod_inverse(long long a, long long mod) {
	long long x, y;
	extgcd(a, mod, &x, &y);
	return (mod + x) % mod;
}

int main() {
	dp[0] = 1;
	int max_coin = 0;
	int coin_count = 0;
	for (const int& coin : COIN) {
		max_coin = max(max_coin, coin);
		coin_count++;
		for (int j = coin; j < MAX; j++) {
			dp[j] = (dp[j] + dp[j - coin]) % MOD;
		}
	}
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> M;
		if (M < MAX) {
			cout << dp[M] << endl;
		} else {
			long long q = M / max_coin;
			long long r = M % max_coin;
			long long res = 0;
			for (int j = 0; j < coin_count; j++) {
				long long term = 1;
				for (int k = 0; k < coin_count; k++) {
					if (k != j) {
						term = (term * ((q - k + MOD) % MOD)) % MOD;
					}
				}
				for (int k = 0; k < coin_count; k++) {
					if (k != j) {
						term = (term * mod_inverse((j - k + MOD) % MOD, MOD)) % MOD;
					}
				}
				res = (res + (term * dp[(j * max_coin + r)]) % MOD) % MOD;
			}
			cout << res << endl;
		}
	}
	return 0;
}