32687번 - 반복수

문제

하나의 $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ドル$비트 정수형 타입을 사용해야 한다.