문자열 나누기

면접 대비

시간 제한1초메모리 제한512 MB

요약

숫자 문자열을 leading zero가 없는 K개의 비어 있지 않은 연속 부분 문자열로 나누는 경우의 수를 1,000,000,007로 나눈 나머지로 구한다.

문제

숫자로 이루어진 문자열 S가 있다. 문자열 S를 K-1번 잘라 K개의 비어있지 않은 연속 부분 문자열로 나눌 때, 어떠한 연속 부분 문자열에도 leading zero가 없도록 나누는 경우의 수를 구해보자.

첫째 줄에 문자열의 길이 N과 연속 부분 문자열의 개수 K가 주어진다. (1 ≤ K ≤ N ≤ 2,500)

둘째 줄에 문자열 S가 주어진다.

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

leading zero는 숫자로 이루어진 문자열에서 0을 제외한 첫 번째 숫자 앞에 오는 모든 숫자 0을 의미한다.

단, "0"은 leading zero에 해당하지 않는다.