Пусть S(n,k,b) обозначает количество верных решений для x₁ + x₂ + ... + x_k ≤ n, где 0 ≤ x_m ≤ b^m для всех 1 ≤ m ≤ k.

Например, S(14,3,2) = 135, S(200,5,3) = 12949440 и S(1000,10,5) mod 1 000 000 007 = 624839075.

Найдите (∑_{10 ≤ k ≤ 15} S(10^k,k,k)) mod 1 000 000 007.