package contest; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Q766_2 { InputStream is; PrintWriter out; String INPUT = ""; int mod = 1000000007; void solve() { char[] a = ns().toCharArray(); char[] b = ns().toCharArray(); int P = ni(); long ret = count(b, P)-count(minus1(a), P)+mod; out.println(ret%mod); } long count(char[] a, int P) { int n = a.length; int q = P == 8 ? n-3 : P == 80 ? n-4 : n-5; q = Math.max(q, 0); long preaho = 0L; long[] pre = new long[3]; // 0,1,2:not-aho long curaho = 0L; long[] cur = new long[3]; pre[0] = 0; int medge = 0, sedge = 0; for(int i = 0;i < q;i++){ curaho = preaho * 10L % mod; Arrays.fill(cur, 0L); for(int j = 0;j < 3;j++){ // for(int k = 0, l = j*10%3;k <= 9;k++,l++){ for(int k = 0, l = j;k <= 9;k++,l++){ if(l == 3)l = 0; if(k == 3){ curaho += pre[j]; if(curaho >= mod)curaho -= mod; }else{ cur[l] += pre[j]; if(cur[l] >= mod)cur[l] -= mod; } } } if(sedge == 0){ for(int k = 0, l = medge;k < a[i]-'0';k++,l++){ if(l == 3)l = 0; if(k == 3){ curaho += 1; if(curaho >= mod)curaho -= mod; }else{ cur[l] += 1; if(cur[l] >= mod)cur[l] -= mod; } } }else{ curaho += a[i]-'0'; if(curaho >= mod)curaho -= mod; } // medge = (medge * 10 + (a[i]-'0')) % 3; medge = (medge + (a[i]-'0')) % 3; if(a[i] == '3')sedge = 1; {long dum = preaho; preaho = curaho; curaho = dum;} {long[] dum = pre; pre = cur; cur = dum; } // tr(a[i], pre, preaho); } // not on edge int D = P*125; long ret = 0; { int[] co = new int[7]; int n3 = 0; for(int i = 0, j = 0, k = 0;i < D;i++,j++,k++){ if(j == P)j = 0; if(k == 3)k = 0; for(int u = 0;u < 7;u++){ if(co[u] == 3)n3--; co[u]++; if(co[u] == 3)n3++; if(co[u] == 10){ co[u] = 0; }else{ break; } } if(j != 0){ if(n3 > 0){ ret += pre[0]+pre[1]+pre[2]+preaho; }else{ ret += pre[(3-k)%3]+preaho; } } } } // on edge { int[] co = new int[7]; int E = 0; int n3 = 0; for(int i = q;i < n;i++)E = E * 10 + a[i]-'0'; for(int i = 0, j = 0, k = 0;i <= E;i++,j++,k++){ if(j == P)j = 0; if(k == 3)k = 0; for(int u = 0;u < 7;u++){ if(co[u] == 3)n3--; co[u]++; if(co[u] == 3)n3++; if(co[u] == 10){ co[u] = 0; }else{ break; } } if(j != 0){ if(sedge == 1){ ret += 1; }else if(n3 > 0){ ret += 1; }else if((medge+k) % 3 == 0){ ret += 1; } } } } return ret%mod; } public static char[] minus1(char[] a) { if(a.length == 1 && a[0] == '0')throw new RuntimeException(); for(int i = a.length-1;i >= 0;i--){ if(--a[i] < '0'){ a[i] = '9'; }else{ break; } } if(a[0] == '0'){ return Arrays.copyOfRange(a, 1, a.length); }else{ return a; } } void run() throws Exception { // int n = 200000, m = 99999; // Random gen = new Random(); // StringBuilder sb = new StringBuilder(); // sb.append(0); // for (int i = 0; i < n-1; i++) { // sb.append(gen.nextInt(10)); // } // sb.append(" "); // for (int i = 0; i < n; i++) { // sb.append(gen.nextInt(10)); // } // sb.append(" "); // sb.append("800"); // INPUT = sb.toString(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); } public static void main(String[] args) throws Exception { new Q766_2().run(); } private byte[] inbuf = new byte[1024]; private int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }