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