#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <fstream>
#include <sstream>
using namespace std;
typedef long long ll;

//const ll MOD = 1000000009ll;

template<ll mod>
struct MOD {
    ll v;
    
    MOD():v(0){}
    MOD(int n):v(n%mod){}
    MOD(ll n):v(n%mod){}
    
    MOD operator+(const MOD& other){
        return (v + other.v) % mod;
    }
    MOD operator-(const MOD& other){
        return (v - other.v + mod) % mod;
    }
    MOD operator*(const MOD& other){
        return (v * other.v) % mod;
    }
    MOD operator^(ll e){
        MOD v = 1;
        MOD x = *this;
        for(;e;e>>=1){
            if(e & 1)v = v * x;
            x = x * x;
        }
        return v;
    }
};

template<ll mod> MOD<mod> operator*(int L, MOD<mod> R){ return MOD<mod>(L) * R; }
template<ll mod> MOD<mod> operator/(MOD<mod> L, int R){ return L * (MOD<mod>(R) ^ (mod - 2)); }

typedef MOD<1000000009> mint;

mint f(mint a, mint b, mint c, mint d, mint e){
    return (25000*((a^4)) + 25000*(a^3)*b + 10000*(a^2)*(b^2) + 2000*a*(b^3) + 200*(b^4) +
          12500*(a^3)*c + 10000*(a^2)*b*c + 3000*a*(b^2)*c + 400*(b^3)*c + 2500*(a^2)*(c^2) +
          1500*a*b*(c^2) + 300*(b^2)*(c^2) + 250*a*(c^3) + 100*b*(c^3) + 2500*(a^3)*d +
          2000*(a^2)*b*d + 600*a*(b^2)*d + 80*(b^3)*d + 1000*(a^2)*c*d + 600*a*b*c*d +
          120*(b^2)*c*d + 150*a*(c^2)*d + 60*b*(c^2)*d + 100*(a^2)*(d^2) + 60*a*b*(d^2) +
          12*(b^2)*(d^2) + 30*a*c*(d^2) + 12*b*c*(d^2) + 1250*(a^3)*e + 1000*(a^2)*b*e +
          300*a*(b^2)*e + 40*(b^3)*e + 500*(a^2)*c*e + 300*a*b*c*e + 60*(b^2)*c*e +
          75*a*(c^2)*e + 30*b*(c^2)*e + 100*(a^2)*d*e + 60*a*b*d*e + 12*(b^2)*d*e +
          30*a*c*d*e + 12*b*c*d*e + 58750*(a^3) + 42000*(a^2)*b + 10100*a*(b^2) +
          680*(b^3) + 21000*(a^2)*c + 10100*a*b*c + 1020*(b^2)*c + 2525*a*(c^2) +
          510*b*(c^2) + 100*(c^3) + 4200*(a^2)*d + 2020*a*b*d + 204*(b^2)*d + 1010*a*c*d +
          204*b*c*d + 60*(c^2)*d + 110*a*(d^2) + 24*b*(d^2) + 12*c*(d^2) + 2100*(a^2)*e +
          1010*a*b*e + 102*(b^2)*e + 505*a*c*e + 102*b*c*e + 30*(c^2)*e + 110*a*d*e +
          24*b*d*e + 12*c*d*e + 31600*(a^2) + 12210*a*b + 742*(b^2) + 6105*a*c +
          742*b*c + 210*(c^2) + 1220*a*d + 148*b*d + 84*c*d + 12*(d^2) + 610*a*e +
            74*b*e + 42*c*e + 12*d*e - 390*a + 274*b + 122*c + 24*d + 12*e + 12)*(a + 1)/12;
}

ll solve(ll M){
    int coins[] = {500, 100, 50, 10, 5};
    ll xs[5];
    
    for(int i=0;i<5;i++){
        xs[i] = M / coins[i];
        M %= coins[i];
    }
    
    mint res = f(xs[0], xs[1], xs[2], xs[3], xs[4]);
    return res.v;
}

int main(){
    int T;
    cin >> T;
    
    while(T--){
        ll M;
        cin >> M;
        
        cout << solve(M) << endl;
    }
    
    return 0;
}