Problem 294
Sum of digits - experience #23
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 < 10n with the following properties :
- k is divisible by 23 and
- d(k) = 23.
You are given that S(9) = 263626 and S(42) = 6377168878570056.
Find S(1112) and give your answer mod 109.
各位数字和——邂逅数23
对于正整数k，记d(k)为k在十进制表示下的各位数字和，例如d(42) = 4+2 = 6。
对于正整数n，记S(n)是满足如下性质的正整数k < 10n的数目：
- k能够被23整除；
- d(k) = 23。
已知S(9) = 263626以及S(42) = 6377168878570056。
求S(1112)，并将你的答案模109取余。