Существует 16 натуральных чисел, не содержащих нулей и имеющих сумму всех своих цифр, равную 5, а именно:
5, 14, 23, 32, 41, 113, 122, 131, 212, 221, 311, 1112, 1121, 1211, 2111 и 11111.
В сумме они дают 17891.

Пусть f(n) будет суммой всех натуральных чисел, не содержащих цифру 0 и имеющих сумму всех цифр равную n.

Найдите $\displaystyle \sum_{i=1}^{17} f(13^i)$.
В качестве ответа приведите последние девять цифр.