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