#include <bits/stdc++.h> #define _overload(_1,_2,_3,name,...) name #define _rep(i,n) _range(i,0,n) #define _range(i,a,b) for(int i=int(a);i<int(b);++i) #define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__) #define _rrep(i,n) _rrange(i,n,0) #define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i) #define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__) #define _all(arg) begin(arg),end(arg) #define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg)) #define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary) template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;} template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;} using namespace std; using ll=long long; const ll mod=1000000009LL; ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;} ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;} ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;} ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;} ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x%mod+mod)%mod,mod);} const int c[6]={1,5,10,50,100,500}; const int limit=3001; ll dp[6][limit]; ll calc(ll n){ ll a=n/500LL,b=n%500LL; ll ret=0LL; rep(i,6){ ll coef=1LL; rep(j,6){ if(j==i) continue; coef=MUL(coef,(mod+a-j)%mod,mod); coef=DIV(coef,(mod+i-j)%mod,mod); } ret=ADD(ret,MUL(coef,dp[5][500*i+b],mod),mod); } return ret; } int main(void){ dp[0][0]=1LL; rep(i,6)rep(j,limit){ if(i-1>=0) dp[i][j]=ADD(dp[i][j],dp[i-1][j],mod); if(j-c[i]>=0) dp[i][j]=ADD(dp[i][j],dp[i][j-c[i]],mod); } int t; cin >> t; rep(loop,t){ ll n; cin >> n; cout << calc(n) << endl; } return 0; }