294 : 桁の合計 - 23の場合

正の整数 k に対し、k を通常の10進数で表したときの桁の合計を d(k) と定義する。つまり d(42) = 4+2 = 6 である。

正の整数 n に対し、S(n) を次の性質を満たす正の整数$k < 10^n$の個数と定義する：

• k は 23 で割り切れる、かつ

• d(k) = 23

S(9) = 263626, S(42) = 6377168878570056 であることがわかる。

$S(11^{12})$を求め、$\mod 10^9$を答えよ。