Problem 685

Inverse Digit Sum II

Writing down the numbers which have a digit sum of $10$ in ascending order, we get: $19, 28, 37, 46, 55, 64, 73, 82, 91, 109, 118, \dots$

Let $f (n, m)$ be the $m^{th}$ occurrence of the digit sum $n$ . For example, $f (10, 1) = 19$ , $f (10, 10) = 109$ and $f (10, 100) = 1423$ .

Let $S (k) = \sum_{n = 1}^{k} f (n^{3}, n^{4})$ . For example $S (3) = 7128$ and $S (10) \equiv 32287064 \mod 1 000 000 007$ .

Find $S (10 000)$ modulo $1 000 000 007$ .

从小到大排列，数字和为 $10$ 的数包括： $19, 28, 37, 46, 55, 64, 73, 82, 91, 109, 118, \dots$

记 $f (n, m)$ 为第 $m$ 个数字和为 $n$ 的数。例如， $f (10, 1) = 19$ ， $f (10, 10) = 109$ ， $f (10, 100) = 1423$ 。

记 $S (k) = \sum_{n = 1}^{k} f (n^{3}, n^{4})$ 。例如 $S (3) = 7128$ ， $S (10) \equiv 32287064 mod 1 000 000 007$ 。

求 $S (10 000)$ 并对 $1 000 000 007$ 取余。