## Constrained Sums

### Problem 528

Let S(`n`,`k`,`b`) represent the number of valid solutions to `x`_{1} + `x`_{2} + ... + `x`_{k} ≤ `n`, where 0 ≤ `x`_{m} ≤ `b`^{m} for all 1 ≤ `m` ≤ `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 (∑_{10 ≤ k ≤ 15} S(10^{k},`k`,`k`)) mod 1 000 000 007.