885 : 数字の整列

正整数 $d$ に対して、$d$ の数字を昇順に整列し、0を除いて作られる数を $f(d)$ としよう。 例えば $f(3403) = 334$ である。

$n$ 桁もしくはそれ未満の全ての正整数 $d$ に対する $f(d)$ の和を $S(n)$ とする。 $S(1) = 45, S(5) = 1543545675$ である。

$S(18) \bmod 1123455689$ を求めよ。