반복수

하나의 $K$자리 수를 원하는 만큼 연속해서 이어 붙인 뒤, 뒤에서부터 $0$개 이상의 연속된 숫자를 제거하여 만들어낸 $K$자리 이상의 수를 $K$-반복수라 한다. 가령, $2\\,462\\,462$는 $3$자리 수 $246$을 세 번 이어 붙인 뒤, 마지막 두 자리 숫자를 제거하여 만들어낸 $3$-반복수이며, $24$는 $3$자리수 미만의 수이므로 $3$-반복수가 아니다.

$A$ 이상 $B$ 이하의 $K$-반복수 중, $M$으로 나누어 떨어지는 수의 개수를 구해보자.

첫째 줄에 정수 $A,B,K,M$이 공백으로 구분되어 주어진다. $(1\le A\le B\le 10^{12};$ $1\le K\le 6;$ $1\le M\le 10^{12})$

$A$ 이상 $B$ 이하의 $K$-반복수 중, $M$으로 나누어 떨어지는 수의 개수를 출력한다.

$10^{12}$는 $32$bit 정수형 타입 변수 범위를 초과할 수 있으므로, C/C++의 long long, Java의 Long 등 $64$비트 정수형 타입을 사용해야 한다.