f = lambda x: x*(x+1)*(x+2)*(x+3)*(x+4)//120 T,*M = map(int,open(0).read().split()) MOD = 10**9+9 p = [0]*2500 p[::500] = [1,-5,10,-10,5] for i in [1,5,10,50,100]: for j in range(i,2500): p[j] = (p[j] + p[j-i])%MOD for m in M: print(sum(f(m//500-i+1)*v for i,v in enumerate(p[m%500::500]))%MOD)