class LagrangeInterpolation:
    def __init__(self, dig, mod):
        self.dig = dig
        self.mod = mod

    def BinPower(self, x):
        k = self.mod - 2
        ret = 1
        while k > 0:
            if k & 1:
                ret = ret * x % self.mod
            x = x * x % self.mod
            k >>= 1
        return ret

    def init(self, X, Y, T):
        ret = 0
        for i in range(self.dig+1):
            A = 1
            B = 1
            for j in range(self.dig+1):
                if i == j:
                    continue
                A *= T - X[j]
                A %= self.mod
                B *= X[i] - X[j]
                B %= self.mod
            ret += (Y[i] * A % self.mod) * self.BinPower(B) % self.mod
            ret %= self.mod
        return ret

mod = 10**9+9
N = 3000
M = [1, 5, 10, 50, 100, 500]
DP = [0] * N
DP[0] = 1
for k in range(6):
    for i in range(N):
        if i - M[k] >= 0:
            DP[i] += DP[i-M[k]]
            DP[i] %= mod
Lag = LagrangeInterpolation(5, mod)
T = int(input())
for _ in range(T):
    M = int(input())
    Rem = M % 500
    X = [i for i in range(Rem,N,500)]
    Y = [DP[i] for i in range(Rem,N,500)]
    print(Lag.init(X, Y, M))