MOD = 10 ** 9 + 9

def lagrange_interpolation(X, Y, MOD):
    def modinv(a):
        b = MOD
        u = 1
        v = 0
        while b:
            t = a // b
            a -= t * b
            u -= t * v
            a, b = b, a
            u, v = v, u
        u %= MOD
        return u

    X = X[:]
    Y = Y[:]
    n = len(X) - 1
    for i in range(n + 1):
        t = 1
        for j in range(n + 1):
            if i != j:
                t *= X[i] - X[j]
                t %= MOD
        Y[i] *= modinv(t)
        Y[i] %= MOD
    dp = [0] * (n + 2)
    dp[0] = -X[0]
    dp[1] = 1
    for i in range(1, n + 1):
        ndp = [0] * (n + 2)
        for j in range(n + 2):
            ndp[j] = -dp[j] * X[i]
            if j >= 1:
                ndp[j] += dp[j - 1]
            ndp[j] %= MOD
        dp = ndp

    inv = [modinv(x) for x in X]
    coef = [0] * (n + 1)
    for i in range(n + 1):
        if Y[i] == 0:
            continue
        if X[i] == 0:
            for j in range(n + 1):
                coef[j] += dp[j + 1] * Y[i] % MOD
                coef[j] %= MOD
        else:
            pre = -dp[0] * inv[i] % MOD
            coef[0] += pre * Y[i] % MOD
            if coef[0] >= MOD:
                coef[0] -= MOD
            for j in range(1, n + 1):
                nex = -(dp[j] - pre) * inv[i] % MOD
                coef[j] += nex * Y[i] % MOD
                if coef[j] >= MOD:
                    coef[j] -= MOD
                pre = nex
    return coef

dp = [0] * 3000
dp[0] = 1
for x in [1, 5, 10, 50, 100, 500]:
    for i in range(x, 3000):
        dp[i] += dp[i - x]
        dp[i] %= MOD

C = []
for i in range(500):
    X = [j for j in range(6)]
    Y = [dp[j] for j in range(i, 3000, 500)]
    C.append(lagrange_interpolation(X, Y, MOD))

for _ in range(int(input())):
    m = int(input())
    x = 1
    ans = 0
    mm = m // 500
    for c in C[m % 500]:
        ans += x * c
        ans %= MOD
        x *= mm
        x %= MOD
    print(ans)