i,s[99999];long m=1e9+9;main(j){for(;i++<9;)for(j=0;j<9e4;s[i+j++]%=m)s[j+i]+=s[j]+(i==1);for(;i=~scanf("%ld",&m);j=0)j||printf("%d\n",s[m/111111+1]);}