import core.thread;
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex;

//	Input
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { tokens = readln.split; if (stdin.eof) throw new EOFException; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return to!int(readToken); }
long readLong() { return to!long(readToken); }
real readReal() { return to!real(readToken); }

//	chmin/chmax
void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

//	Pair
struct Pair(S, T) {
	S x; T y;
	int opCmp(    const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	int opCmp(ref const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	string toString() const { return "(" ~ to!string(x) ~ ", " ~ to!string(y) ~ ")"; }
}
auto pair(S, T)(inout(S) x, inout(T) y) { return Pair!(S, T)(x, y); }

//	Array
int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = as.length; for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <  val); }); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <= val); }); }
T[] unique(T)(in T[] as) { T[] bs; foreach (a; as) if (bs.empty || bs[$ - 1] != a) bs ~= a; return bs; }


immutable long MO = 10^^9 + 9;

long modInv(long x) {
	long y = 1, e = MO - 2;
	for (; e; e >>= 1, (x *= x) %= MO) if (e & 1) (y *= x) %= MO;
	return y;
}

//	f(0), ..., f(deg)
long[] interpolation(in long[] _ys) {
	long[] ys = _ys.dup;
	const n = ys.length - 1;
	foreach (i; 1 .. n + 1) {
		foreach_reverse (j; i .. n + 1) {
			((ys[j] -= ys[j - 1]) *= modInv(i)) %= MO;
		}
	}
	long[] ret = new long[n + 1];
	ret[0] = ys[0];
	long[] prod = new long[n];
	prod[0] = 1;
	foreach (i; 1 .. n + 1) {
		foreach (j; 0 .. i) {
			(ret[i - j] += prod[j] * ys[i]) %= MO;
		}
		if (i == n) {
			break;
		}
		foreach_reverse (j; 0 .. i) {
			(prod[j + 1] -= i * prod[j]) %= MO;
		}
	}
	foreach (i; 0 .. n + 1) {
		ret[i] = (ret[i] % MO + MO) % MO;
	}
	return ret;
}

immutable L = 500;
immutable D = 10;

void main(string[] args) {
	long[] dp = new long[L * (D + 1)];
	dp[0] = 1;
	foreach (w; [ 1, 5, 10, 50, 100, 500 ]) {
		foreach (x; w .. L * (D + 1)) {
			(dp[x] += dp[x - w]) %= MO;
		}
	}
	
	long[][] polys = new long[][L];
	foreach (l; 0 .. L) {
		long[] ys = new long[D + 1];
		foreach (j; 0 .. D + 1) {
			ys[j] = dp[j * L + l];
		}
		polys[l] = ys.interpolation;
debug{
if(l<=10)writeln(ys," ",polys[l]);
}
	}
	
	foreach (tc; 0 .. readInt) {
		long m = readLong;
		const x = (m / L) % MO;
		const l = cast(size_t)(m % L);
		long ans;
		foreach_reverse (j; 0 .. D + 1) {
			ans = (ans * x + polys[l][j]) % MO;
		}
		ans = (ans % MO + MO) % MO;
		writeln(ans);
	}
}