For a positive integer k, define d(k) as the sum of the digits of k in its usual decimal representation. Thus d(42) = 4+2 = 6.
For a positive integer n, define S(n) as the number of positive integers k n with the following properties :
Find S(1112) and give your answer mod 109.
These problems are part of Project Euler and are licensed under CC BY-NC-SA 2.0 UK