#include <stdio.h>
#define M 1000000
int A[M+1],i;
int main(z){
	A[0]=1;
	for(;z<=9;z++)for(i=0;i<=M-z;i++)A[i+z]=(A[i+z]+A[i])%1000000009;
	for(i=0;i<M;i++)A[i+1]=(A[i+1]+A[i])%1000000009;
	long long m;
	for(scanf("%d",&m);~scanf("%lld",&m);){
		printf("%d\n",A[m/111111]);
	}return 0;
}