Constrained Sums

Let $S (n, k, b)$ represent the number of valid solutions to $x_{1} + x_{2} + \dots + x_{k} \leq n$ , where $0 \leq x_{m} \leq b^{m}$ for all $1 \leq m \leq k$ .

For example, $S (14, 3, 2) = 135$ , $S (200, 5, 3) = 12949440$ , and $S (1000, 10, 5) mod 1 000 000 007 = 624839075$ .

Find $(\sum_{10 \leq k \leq 15} S (10^{k}, k, k)) mod 1 000 000 007$ .

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.