#[allow(unused_imports)]
use std::io::{stdin, Read, StdinLock};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BinaryHeap, VecDeque};
#[allow(unused_imports)]
use std::vec::Vec;

#[allow(dead_code)]
const INF: i32 = 1000_000_000;
#[allow(dead_code)]
const INFLL: i64 = 1000_000_000_000_000_000;
#[allow(dead_code)]
const EPS: f64 = 1.0e-10;
#[allow(dead_code)]
const MOD: i32 = 1000_000_007;
#[allow(dead_code)]
const MODLL: i64 = 1000_000_007;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner {cin: cin}
    }
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
                    .skip_while(|c| c.is_whitespace())
                    .take_while(|c| !c.is_whitespace())
                    .collect::<String>();
        token.parse::<T>().ok()
    }
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

fn solve(a: String, m: usize, f: usize) -> i32 {
    // dp[i][less][mod m][pre][up]
    let a: Vec<char> = a.chars().collect();
    let mut dp: Vec<Vec<Vec<Vec<Vec<i32>>>>> = vec![vec![vec![vec![vec![0; 2]; 10]; m]; 2]; a.len() + 1];
    for i in 0..a.len() {
        let cur = a[i].to_digit(10).unwrap();
        for le in 0..2 {
            for j in 0..m {
                for pre in 0..10 {
                    for k in 0..2 {
                        let lb = if k == 1 { pre + 1 } else { 0 };
                        let ub = if le == 1 { 10 } else { cur + 1 };
                        let ub = if k == 0 { min(ub, pre) } else { ub };
                        if lb >= ub {
                            continue;
                        }
                        for d in lb..ub {
                            let nle: usize = if le == 1 || d < cur { 1 } else { 0 };
                            let nk: usize = if k == 0 { 1 } else { 0 };
                            let nj: usize = (j * 10 + d as usize) % m;
                            let d = d as usize;
                            let pre = pre as usize;
                            dp[i + 1][nle][nj][d][nk] += dp[i][le][j][pre][k];
                            dp[i + 1][nle][nj][d][nk] %= 10000;
                        }
                    }
                }
            }
        }
        let ub = if i == 0 { cur + 1 } else { 10 };
        for j in 1..ub {
            let le = if i != 0 || j != cur { 1 } else { 0 };
            let le = le as usize;
            let j = j as usize;
            dp[i + 1][le][j % m][j][0] += 1;
            if i + 1 != a.len() {
                dp[i + 1][le][j % m][j][1] += 1;
            }
        }
    }

    let mut ans = 0;
    for i in 0..10 {
        for j in 0..2 {
            ans = (ans + dp[a.len()][1][0][i][j]) % 10000;
            if f == 1 {
                ans = (ans + dp[a.len()][0][0][i][j]) % 10000;
            }
        }
    }
    ans
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let (a, b, m): (String, String, usize) = (sc.read(), sc.read(), sc.read());
    let x = solve(a, m, 0);
    let y = solve(b, m, 1);
    let ans = (y - x + 10000) % 10000;
    println!("{}", ans);
}


Measured memory_bytes: 185240