This question doesn't support checking answers.

528. Constrained Sums

Let S(n,k,b) represent the number of valid solutions to x₁ + x₂ + ... + 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.