MOD = 10 ** 9 + 9
invs = [0] * 100
invs[1] = 1
for i in range(2, 100):
    invs[i] = (invs[MOD % i] * (MOD - MOD // i)) % MOD

C = [1, 1, 2, 10, 20, 100]
p = [1]
for i in range(5):
    np = [0] * (len(p) + 100 - C[i])
    for j in range(0, 100, C[i]):
        for k in range(len(p)):
            np[j + k] += p[k]
    p = np
T = int(input())
for _ in range(T):
    n = int(input()) // 5
    m = MOD + n // 100 % MOD
    r = n % 100
    ans = 0
    while r < len(p) and r <= n:
        b = 1
        for i in range(5):
            b = b * (m + 5 - i) % MOD * invs[i + 1] % MOD
        ans += p[r] * b % MOD
        r += 100
        m -= 1
    print(ans % MOD)