fun main(args: Array<String>?): Unit {
    val a = readLine()!!.trim()
    val b = readLine()!!.trim()
    val m = readLine()!!.trim().toInt()
    println(solve(a, b, m))
}
fun solve(from: String, to: String, m: Int): Int {
    val mod = 10000
    val digitRest = IntArray(to.length){0}
    digitRest[digitRest.lastIndex] = 1
    for (i in digitRest.lastIndex - 1 downTo 0) digitRest[i] = (digitRest[i + 1] * 10) % m
    val memo = Array(2){Array(10){Array(m){IntArray(to.length){-1}}}}
    fun setMemo(digit: Int, currentDigit: Int, rest: Int, toDown: Boolean): Int {
        if (digit == to.length - 1) return if ((rest + digitRest[digit] * currentDigit) % m == 0) 1 else 0
        if (memo[toDown][currentDigit][rest][digit] == -1){
            memo[toDown][currentDigit][rest][digit] = (if (toDown)
                (0 until currentDigit).sumBy { d -> setMemo(digit + 1, d, (rest + digitRest[digit] * currentDigit) % m, !toDown) }
            else
                (currentDigit + 1 until 10).sumBy{ d -> setMemo(digit + 1, d, (rest + digitRest[digit] * currentDigit) % m, !toDown)}) % mod
        }
        return memo[toDown][currentDigit][rest][digit]
    }
    fun countBelow(digits: IntArray, digit: Int, rest: Int, toDown: Boolean): Int {
        if (digit == digits.size - 1) return if ((rest + digitRest[digit] * digits[digit]) % m == 0) 1 else 0
        var result = 0
        if (toDown) {
            if (digits[digit] > digits[digit + 1]) {
                result += countBelow(digits, digit + 1, (rest + digitRest[digit] * digits[digit]) % m, !toDown)
                for (d in 0 until digits[digit + 1]) {
                    result += setMemo(digit + 1, d, (rest + digitRest[digit] * digits[digit]) % m, !toDown)
                }
            }else {
                for (d in 0 until digits[digit]) {
                    result += setMemo(digit + 1, d, (rest + digitRest[digit] * digits[digit]) % m, !toDown)
                }
            }
        }else {
            if (digits[digit] < digits[digit + 1]) {
                result += countBelow(digits, digit + 1, (rest + digitRest[digit] * digits[digit]) % m, !toDown)
                for (d in digits[digit] + 1 until digits[digit + 1]) {
                    result += setMemo(digit + 1, d, (rest + digitRest[digit] * digits[digit]) % m, !toDown)
                }
            }
        }
        return result % mod
    }
    val fromDigits = IntArray(to.length){0}
    val toDigits = to.map{it - '0'}.toIntArray()
    for (i in from.indices) {
        fromDigits[fromDigits.lastIndex - i] = from[from.lastIndex - i] - '0'
    }
    var borrow = -1
    for (i in fromDigits.lastIndex downTo 0){
        fromDigits[i] += borrow
        if (fromDigits[i] < 0) {
            fromDigits[i] += 10
        }else {
            borrow = 0
        }
    }
    val firstDigit = fromDigits.indices.find{fromDigits[it] != 0} ?: fromDigits.lastIndex
    val belowTo = if (toDigits.size != 1) {
        (countBelow(toDigits, 0, 0, true) + countBelow(toDigits, 0, 0, false) +
                (1 until toDigits[0]).sumBy { d -> setMemo(0, d, 0, true) + setMemo(0, d, 0, false) } +
                (1 until toDigits.lastIndex).sumBy { digit -> (1 until 10).sumBy { d -> setMemo(digit, d, 0, true) + setMemo(digit, d, 0, false) } } +
                (0 until 10).sumBy{d -> setMemo(toDigits.lastIndex, d, 0, true)}) % mod
    } else {
        (0 .. toDigits[0]).sumBy{d -> setMemo(0, d, 0, true)} % mod
    }
    val belowFrom = if (from.length != 1) {
        (countBelow(fromDigits, firstDigit, 0, true) + countBelow(fromDigits, firstDigit, 0, false) +
                (1 until fromDigits[firstDigit]).sumBy { d -> setMemo(firstDigit, d, 0, true) + setMemo(firstDigit, d, 0, false) } +
                (firstDigit + 1 until fromDigits.lastIndex).sumBy { digit -> (1 until 10).sumBy { d -> setMemo(digit, d, 0, true) + setMemo(digit, d, 0, false) } } +
                (0 until 10).sumBy{d -> setMemo(fromDigits.lastIndex, d, 0, true)}) % mod
    } else {
        (0 .. fromDigits[fromDigits.lastIndex]).sumBy{d -> setMemo(fromDigits.lastIndex, d, 0, true)} % mod
    }
    return (belowTo - belowFrom + mod) % mod
}
operator fun <T> Array<T>.get(bool: Boolean): T {
    return this[if (bool) 1 else 0]
}


Measured memory_bytes: 55632