https://www.acmicpc.net/problem/16933
import java.io.File
import java.util.StringTokenizer
// input
private var br = System.`in`.bufferedReader()
// variables
private var A: Long = 0
private var B: Long = 0
private var K = 0
private var M: Long = 0
fun main() {
val bw = System.out.bufferedWriter()
input()
bw.write(solve())
bw.close()
} // End of main()
private fun solve(): String {
val sb = StringBuilder()
var ans: Long = 0
var start: Long = Math.pow(10.0, (K - 1).toDouble()).toLong()
var end: Long = (Math.pow(10.0, K.toDouble()) - 1).toLong()
var i: Long = 0
for (i in start..end) {
var str = i.toString()
var cur = i
var idx = 0
while (cur <= B) {
if (A <= cur && cur <= B && cur % M == 0L) {
ans++
}
cur = cur * 10 + (str[idx] - '0')
idx = (idx + 1) % str.length
}
}
sb.append(ans)
return sb.toString()
} // End of solve()
private fun input() {
StringTokenizer(br.readLine()).run {
A = nextToken().toLong()
B = nextToken().toLong()
K = nextToken().toInt()
M = nextToken().toLong()
}
} // End of input()