#define M 1000000
A[M+1]={1},i,z;main(y){
	for(z=10;z--;)for(i=0;i<=M-(z+!z);i++)A[i+z+!z]=(A[i+z+!z]+A[i])%1000000009;
	long long m;
	for(;~scanf("%lld",&m);)--y&&printf("%d\n",A[m/111111]);
}