---

Problem 885

---

Sorted Digits

For a positive integer $d$, let $f(d)$ be the number created by sorting the digits of $d$ in ascending order, removing any zeros. For example, $f(3403) = 334$.

Let $S(n)$ be the sum of $f(d)$ for all positive integers $d$ of $n$ digits or less. You are given $S(1) = 45$ and $S(5) = 1543545675$.

Find $S(18)$. Give your answer modulo $1123455689$.

---

数字排序

对于正整数$d$，记$f(d)$为将$d$的各位非零数字按升序排序所得的结果。例如，$f(3403) = 334$。

记$S(n)$为所有至多$n$位的正整数$d$所对应的$f(d)$之和。已知$S(1) = 45$，$S(5) = 1543545675$。

求$S(18)$，并对$1123455689$取余作为你的答案。

---