import sys # Increase recursion depth limit for potentially very long numbers. # The maximum length of A and B is 200000 according to the problem statement. # Setting it slightly higher for safety margin. # Note: On some systems or platforms, the maximum recursion depth might be limited by OS. # Competitive programming platforms usually allow high limits. try: sys.setrecursionlimit(200000 + 10) except OverflowError: # If setting the limit causes an OverflowError (rare, possibly due to system constraints) # fall back to a default large value. Adjust if needed based on platform specifics. sys.setrecursionlimit(2000) MOD = 10**9 + 7 # Memoization dictionary to store results of DP states memo = {} # Input number N as a string, used by the DP function S = "" # Divisor P, given in the input (8, 80, or 800) P = 0 # The core digit DP function # Arguments: # idx: current digit index being processed (from left, 0-based) # tight: boolean flag, True if we are restricted by the digits of N, False otherwise # is_leading_zero: boolean flag, True if we are currently placing leading zeros # has_digit_3: boolean flag, True if any digit '3' has been placed so far (ignoring leading zeros) # rem_3: the remainder of the number formed so far when divided by 3 # rem_P: the remainder of the number formed so far when divided by P def dp(idx, tight, is_leading_zero, has_digit_3, rem_3, rem_P): # Base case: If we have processed all digits if idx == len(S): # If the number constructed consists of only leading zeros (effectively the number 0) # it doesn't satisfy the condition A >= 1. We count numbers in [1, N]. # So, return 0 for the number 0. if is_leading_zero: return 0 # Check the conditions specified in the problem: # Condition "Aho": number is multiple of 3 OR contains digit 3 is_aho = (rem_3 == 0) or has_digit_3 # Condition "Hajirai": number is multiple of P is_hajirai = (rem_P == 0) # We need numbers that are "Aho" AND NOT "Hajirai" if is_aho and not is_hajirai: return 1 # Count this number else: return 0 # Do not count this number # Create a tuple representing the current state for memoization key state = (idx, tight, is_leading_zero, has_digit_3, rem_3, rem_P) # Check if the result for this state is already computed and stored in memo if state in memo: return memo[state] # Initialize the result for the current state to 0 res = 0 # Determine the upper limit for the current digit 'd' # If 'tight' is True, limit is the digit S[idx], otherwise it's 9 limit = int(S[idx]) if tight else 9 # Iterate through all possible digits 'd' for the current position 'idx' for d in range(limit + 1): # Determine the 'tight' constraint for the next recursive call # It remains True only if the current 'tight' is True AND we chose the maximum possible digit 'd' new_tight = tight and (d == limit) # Store current remainders before potential updates. This helps clarify logic especially # when transitioning from leading zero state. current_rem_3 = rem_3 current_rem_P = rem_P # Handle the case where we are currently placing leading zeros if is_leading_zero and d == 0: # If current digit is 0 and we were placing leading zeros, we continue doing so. # The state related to digit 3 and remainders doesn't change substantively (remains 0). # The 'has_digit_3' flag remains False. res = (res + dp(idx + 1, new_tight, True, False, 0, 0)) % MOD else: # If current digit 'd' is non-zero, or if we were already past the leading zeros phase: # If we are placing the first non-zero digit (transitioning from leading zero state) if is_leading_zero: # The previous number value was 0, so start remainders based on 'd' current_rem_3 = 0 current_rem_P = 0 # The number is no longer considered zero. Update state accordingly. new_is_leading_zero = False # We are past leading zeros now # Update the has_digit_3 flag: True if it was already True, or if the current digit 'd' is 3. new_has_digit_3 = has_digit_3 or (d == 3) # Calculate the new remainder modulo 3 new_rem_3 = (current_rem_3 * 10 + d) % 3 # Calculate the new remainder modulo P new_rem_P = (current_rem_P * 10 + d) % P # Recursively call the DP function for the next digit position (idx + 1) # with updated state variables, and add the returned count to 'res'. res = (res + dp(idx + 1, new_tight, new_is_leading_zero, new_has_digit_3, new_rem_3, new_rem_P)) % MOD # Store the computed result for the current state in the memoization table memo[state] = res return res # Function to compute F(N): the count of numbers x such that 1 <= x <= N # satisfying the conditions (Aho and not Hajirai). def solve(N_str): global S, memo, P # Need access to global variables S, memo, P S = N_str # Clear the memoization table for each new call to solve() with a different N memo = {} # Handle edge cases: if N_str represents 0 or is empty. # The problem constraints state A >= 1, so N will be at least '1' for F(B), # and at least '0' for F(A-1). F(0) is 0. if not S or S == '0': return 0 # Initial call to the DP function: # Start at index 0. # 'tight' is True because we are constrained by the digits of N. # 'is_leading_zero' is True initially. # 'has_digit_3' is False initially. # 'rem_3' and 'rem_P' are 0 initially. return dp(0, True, True, False, 0, 0) # Function to subtract 1 from a number represented as a string. # Handles large numbers that don't fit into standard integer types. def subtract_one(N_str): # If input is "0", subtracting 1 is not defined in positive integers context. # But for calculating F(A-1), if A=1, A-1=0. We handle F(0) directly. # This function should return "0" when input is "1". if N_str == '1': return "0" if N_str == '0': return "0" # Defensive check, F(0)=0 handled in main logic n = len(N_str) num = list(N_str) i = n - 1 # Standard subtraction algorithm (borrowing from left) while i >= 0: if num[i] == '0': num[i] = '9' # Borrow: change '0' to '9' i -= 1 # Move left to borrow else: num[i] = str(int(num[i]) - 1) # Subtract 1 from non-zero digit break # Borrowing chain stops # If the subtraction resulted in a leading zero (e.g., "100" -> "099") # and the number has more than one digit. if num[0] == '0' and n > 1: # Return the string without the leading zero return "".join(num[1:]) else: # Otherwise return the resulting string (handles single digits correctly, e.g., "1" -> "0") return "".join(num) # Read input using sys.stdin.readline for potentially faster I/O than input() A_str, B_str, P_str = sys.stdin.readline().split() P = int(P_str) # Calculate F(B), the count of valid numbers up to B count_B = solve(B_str) # Calculate the string representation of A-1 A_minus_1_str = subtract_one(A_str) # Calculate F(A-1), the count of valid numbers up to A-1 # The solve function correctly handles N_str = "0" by returning 0. count_A_minus_1 = solve(A_minus_1_str) # The final answer is F(B) - F(A-1). # Compute the result modulo MOD. Add MOD before taking modulo to handle potential negative result. ans = (count_B - count_A_minus_1 + MOD) % MOD print(ans)