# Problem 528: Constrained Sums

![graphic](img528.gif)

Let S(n,k,b) represent the number of valid solutions to x1 + x2 + ... +
xk ≤ n, where 0 ≤ xm ≤ bm 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(10k,k,k)) mod 1 000 000 007.