import java.util.*; public class Main { public static long MOD = (long)Math.pow(10, 9) + 7; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.next(); String B = sc.next(); int p = sc.nextInt(); long ans = (func(B, p) - func(A, p) + MOD) % MOD; int m1 = 0; int kosuu = 0; int m2 = 0; for(int i = 0; i < A.length(); i++) { int d = Integer.parseInt(String.valueOf(A.charAt(i))); if(d == 3) kosuu++; m1 = (m1 + d) % 3; m2 = (10 * m2 + d) % p; } if(((m1 == 0) || (kosuu > 0)) && (m2 != 0)) ans = (ans + 1) % MOD; System.out.println(ans); } public static long func(String X, int p) { int len = X.length(); long[][][][] dp = new long[3][2][p][2]; long[][][][] s = new long[3][2][p][2]; int first = Integer.parseInt(String.valueOf(X.charAt(0))); dp[0][0][0][1]++; if(first == 3) { if((len - 5) <= 0) { dp[(first) % 3][1][(first) % p][0]++; } else { dp[(first) % 3][1][0][0]++; } } else { if((len - 5) <= 0) { dp[(first) % 3][0][(first) % p][0]++; } else { dp[(first) % 3][0][0][0]++; } } for(int i = 1; i < first; i++) { if(i == 3) { if((len - 5) <= 0) { dp[i % 3][1][i % p][1]++; } else { dp[i % 3][1][0][1]++; } } else { if((len - 5) <= 0) { dp[i % 3][0][i % p][1]++; } else { dp[i % 3][0][0][1]++; } } } for(int j = 0; j < 3; j++) { for(int k = 0; k < 2; k++) { for(int m = 0; m < p; m++) { for(int l = 0; l < 2; l++) { s[j][k][m][l] = dp[j][k][m][l]; } } } } for(int i = 1; i < len; i++) { int d = Integer.parseInt(String.valueOf(X.charAt(i))); if((len - 5) <= i) { for(int j = 0; j < 3; j++) { for(int k = 0; k < p; k++) { for(int l = 0; l <= d; l++) { if(l == d) { if(l == 3) { dp[(j + l) % 3][1][(10 * k + l) % p][0] = (dp[(j + l) % 3][1][(10 * k + l) % p][0] + s[j][0][k][0]) % MOD; } else { dp[(j + l) % 3][0][(10 * k + l) % p][0] = (dp[(j + l) % 3][0][(10 * k + l) % p][0] + s[j][0][k][0]) % MOD; } } else { if(l == 3) { dp[(j + l) % 3][1][(10 * k + l) % p][1] = (dp[(j + l) % 3][1][(10 * k + l) % p][1] + s[j][0][k][0]) % MOD; } else { dp[(j + l) % 3][0][(10 * k + l) % p][1] = (dp[(j + l) % 3][0][(10 * k + l) % p][1] + s[j][0][k][0]) % MOD; } } } for(int l = 0; l <= 9; l++) { if(l == 3) { dp[(j + l) % 3][1][(10 * k + l) % p][1] = (dp[(j + l) % 3][1][(10 * k + l) % p][1] + s[j][0][k][1]) % MOD; } else { dp[(j + l) % 3][0][(10 * k + l) % p][1] = (dp[(j + l) % 3][0][(10 * k + l) % p][1] + s[j][0][k][1]) % MOD; } } for(int l = 0; l <= d; l++) { if(l == d) { dp[(j + l) % 3][1][(10 * k + l) % p][0] = (dp[(j + l) % 3][1][(10 * k + l) % p][0] + s[j][1][k][0]) % MOD; } else { dp[(j + l) % 3][1][(10 * k + l) % p][1] = (dp[(j + l) % 3][1][(10 * k + l) % p][1] + s[j][1][k][0]) % MOD; } } for(int l = 0; l <= 9; l++) { dp[(j + l) % 3][1][(10 * k + l) % p][1] = (dp[(j + l) % 3][1][(10 * k + l) % p][1] + s[j][1][k][1]) % MOD; } } } } else { for(int j = 0; j < 3; j++) { for(int l = 0; l <= d; l++) { if(l == d) { if(l == 3) { dp[(j + l) % 3][1][0][0] = (dp[(j + l) % 3][1][0][0] + s[j][0][0][0]) % MOD; } else { dp[(j + l) % 3][0][0][0] = (dp[(j + l) % 3][0][0][0] + s[j][0][0][0]) % MOD; } } else { if(l == 3) { dp[(j + l) % 3][1][0][1] = (dp[(j + l) % 3][1][0][1] + s[j][0][0][0]) % MOD; } else { dp[(j + l) % 3][0][0][1] = (dp[(j + l) % 3][0][0][1] + s[j][0][0][0]) % MOD; } } } for(int l = 0; l <= 9; l++) { if(l == 3) { dp[(j + l) % 3][1][0][1] = (dp[(j + l) % 3][1][0][1] + s[j][0][0][1]) % MOD; } else { dp[(j + l) % 3][0][0][1] = (dp[(j + l) % 3][0][0][1] + s[j][0][0][1]) % MOD; } } for(int l = 0; l <= d; l++) { if(l == d) { dp[(j + l) % 3][1][0][0] = (dp[(j + l) % 3][1][0][0] + s[j][1][0][0]) % MOD; } else { dp[(j + l) % 3][1][0][1] = (dp[(j + l) % 3][1][0][1] + s[j][1][0][0]) % MOD; } } for(int l = 0; l <= 9; l++) { dp[(j + l) % 3][1][0][1] = (dp[(j + l) % 3][1][0][1] + s[j][1][0][1]) % MOD; } } } for(int j = 0; j < 3; j++) { for(int k = 0; k < 2; k++) { for(int m = 0; m < p; m++) { for(int l = 0; l < 2; l++) { s[j][k][m][l] = dp[j][k][m][l]; } } } } } long ret = 0; for(int k = 1; k < p; k++) { for(int l = 0; l < 2; l++) { ret = (ret + dp[0][0][k][l]) % MOD; } } for(int k = 1; k < p; k++) { for(int l = 0; l < 2; l++) { for(int j = 0; j < 3; j++) { ret = (ret + dp[j][1][k][l]) % MOD; } } } return ret; } }