Для положительного целого числа $d$ пусть $f(d)$ будет числом, образованным путем сортировки цифр числа $d$ в возрастающем порядке и удаления всех нулей. Например, $f(3403) = 334$.

Пусть $S(n)$ будет суммой $f(d)$ для всех положительных целых чисел $d$, содержащих не больше $n$ цифр. Известно, что $S(1) = 45$ и $S(5) = 1543545675$.

Найдите $S(18)$. В качестве ответа приведите остаток от деления полученного числа на $1123455689$.