#include using namespace std; #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++) typedef long long llong; char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; char moji3[10]={'0','1','2','3','4','5','6','7','8','9'}; #define Sort(a) sort(a.begin(),a.end()); #define Reverse(a) reverse(a.begin(),a.end()); #define print(a) cout << a << endl; #define MOD llong(1e9 +7) #define MAX 20005 int main(){ llong ans[2]; string S[2]; int p; cin >> S[0] >> S[1] >> p; REP(iiii,2){ string s; s = S[iiii]; int n = s.length(); llong dp[MAX][2][2][3][800]; REP(i,n+1) REP(j,2) REP(k,2) REP(ii,3) REP(jj,p) dp[i][j][k][ii][jj] = 0; dp[0][0][0][0][0] = 1; FOR(i,1,n+1){ REP(j,2){ REP(ii,2){ REP(jj,3){ REP(kk,p){ int lim = j ? 9 : s[i-1] - '0'; REP(k,lim +1){ dp[i][j or k < lim][ii or k == 3][(jj + k) % 3][(kk * 10 + k)%p] += dp[i-1][j][ii][jj][kk]; dp[i][j or k < lim][ii or k == 3][(jj+k) % 3][(kk * 10 + k)%p] %=MOD; } } } } } } ans[iiii] = 0; REP(i,2){ if(iiii == 0 and i == 0) continue; REP(j,2) REP(k,3) FOR(ii,1,p){ if(j== 0 and k != 0) continue; ans[iiii] += dp[n][i][j][k][ii]; ans[iiii] %=MOD; } } } cout << (MOD + ans[1] - ans[0]) % MOD << endl; }