Serial Numbers with Multiplicative Digit Sums

Problem Statement

A factory stamps a serial number on every unit it produces. For a positive integer n , let S(n) denote the sum of the decimal digits of n . A multiplier k is fixed. The factory wants to know, for how many serial numbers n in the range 10 l ≤ n ≤ 10 r − 1 , the condition S(k · n) = k · S(n) holds. Because the count can be enormous, report it modulo 10 9 + 7 . Input Format A single line containing three integers l , r and k , separated by spaces. Output Format Print one integer — the number of valid serial numbers, taken modulo 10 9 + 7 . Constraints 1 ≤ k ≤ 10 9 0 ≤ l < r ≤ 10 9 Sample Input 1 0 1 4 Sample Output 1 2 Explanation. The range is 10 0 = 1 to 10 1 − 1 = 9 . For n = 1 : S(4) = 4 and 4 · S(1) = 4 . For n = 2 : S(8) = 8 and 4 · S(2) = 8 . No other value works, so the answer is 2. Sample Input 2 0 2 7 Sample Output 2 3 Explanation. In 1 … 99 only 1 , 10 and 11 satisfy S(7n) = 7 · S(n) .