숫자

보바가 또 실수를 저질렀다. 그는 출력 파일에 숫자들을 공백 없이 붙여서 출력하고 말았다. 결과를 본 보바는 경악했다. 그러나 곧 그는, 그 숫자들을 공백 없이 이어 붙였을 때 보바의 결과와 같아지는 음이 아닌 정수 수열이 몇 개나 되는지 궁금해졌다. 그는 자신의 프로그램이 아무 숫자나 출력할 수 있는 게 아니라 $C$ 이하의 숫자만, 그것도 앞에 0을 붙이지 않고 출력한다는 것을 기억해 냈다.

그래서 그는 각 수가 $C$를 넘지 않는 음이 아닌 정수 수열의 개수를 구하기로 했다. 그 수가 꽤 클 수 있으므로, 그는 그 수의 마지막 $k$자리만 알면 충분하다.

첫째 줄에 세 정수 $n$, $C$, $k$가 주어진다 ($1 \le n \le 50000$, $1 \le C \le 10^8$, $1 \le k \le 18$). 둘째 줄에는 $n$자리 숫자로 이루어진 문자열, 즉 보바 프로그램의 결과가 주어진다.

찾고자 하는 수열의 개수의 마지막 $k$자리를 출력한다 (앞에 0을 붙이지 않는다).