#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

int mod = 1000000009;

int extgcd(int a, int b ,int &x, int&y){
  int d = a;
  if( b != 0 ){
    d = extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1,y=0;
  }
  return d;
}
int mod_inverse( int a, int m ){
  int x, y ;
  extgcd( a, m , x, y);
  return (m+x%m)%m;
}

using namespace std;
int main(){
   int T;
   cin >> T;
   int coin[]={1,5,10,50,100,500};

   long long dp[3001];
   fill(dp,dp+3001,1);
   for( int ci= 1; ci < 6; ci++ ){
      for( int price = 0 ; price < 3001; price++){
         if(price-coin[ci]>=0){
            dp[price]+=dp[price-coin[ci]];
            dp[price]%=mod;
         }
      }
   }
   for( int ti=0;ti<T;ti++){
      long long ans=0;
      long long M;
      cin >> M;
      long long t = M/500;
      long long r = M%500;
      // M= t*500+r
      // calculate ans(t) using ans(0)=dp[0*500+r], ans(1)=dp[1*500+r],... ans(5)=dp[5*500+r]
      // ans(t) = ans(0)* (t-1)(t-2)(t-3)(t-4)(t-5)/(0-1)(0-2)(0-3)(0-4)(0-5)
      //        + ans(1)* (t-0)(t-2)(t-3)(t-4)(t-5)/(1-0)(1-2)(1-3)(1-4)(1-5)
      //        + ...
      for( int k = 0 ; k <6 ; k++ ){
         long long a = dp[k*500+r];
         //cout << a << "= "<< "dp"<<k<<"*500+"<<r<<endl;
         for( int l = 0 ; l < 6 ; l++ ){
            if( k!=l ){
               a *= (t-l)%mod;
               a %= mod;
               a *= mod_inverse((k-l+mod)%mod,mod);
               a%=mod;
            }
         }
         ans += a;
         ans += mod;
         ans %= mod;
      }
      cout << ans << endl;
   }
   return 0;
}