for((i=0;i<90001;d[i++]=1)){ :;}
for((j=1;j<=9;++j)){
for((i=0;i<90001;d[i+j]=(d[i+j]+d[i])%1000000009,++i)){ :;}
}
read
while read m
do
echo ${d[m/111111]}
done