#define M 1000000
A[M+1]={1},i;main(z){
	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("%d",&m);~scanf("%lld",&m);)printf("%d\n",A[m/111111]);
	exit(0);
}