Problem Statement

Let S(n) represent the sum of the digits of n. The factory wants to know for how many serial numbers n in the range 10^l<= n <= 10^r the condition S(k·n)=k·S(n) holds, where k is a given multiplier. You need to determine how many such serial numbers exist and output the answer modulo 10^9 +7. Input Format First line contains three integers l,r and k. Output Format Print the integer modulo 10^9+7 Constraints 1<=k<=10^9 0 <= l< r <= 10^9 Sample Testcase 1 Testcase Input 0 1 4 Testcase Output 2 Explanation Input: 0 1 4 Range: From 10^0=1 to 10^1-1=9 Condition: Check if S(4·n)=4·S(n). Valid Numbers: S(4·1)=4 and 4·S(1)=4 (Condition satisfied) S(4·2)=8 and 4·S(2)=8 (Condition satisfied) Count: 2 numbers Sample Testcase 2 Testcase Input 0 2 7 Testcase Output 3 Explanation input: 0 2 7 Range: From 10^0 =1 to 10^2-1=99 1 Condition: Check if S(7·n)=7·S(n) Valid Numbers: S(7·1)=7 and 7·S(1)=7 (Condition satisfied) 10: S(7·10)=7 and 7·S(10)=7 (Condition satisfied) 11: S(7·11)