사이클

마리 미슬라프는 자기 도시 근처 사바강의 잔잔한 지류에서 지금도 수련 잎을 찾아간다. 강가를 따라 n개의 수련 잎이 자라며, 왼쪽에서 오른쪽으로 1부터 n까지 번호가 붙어 있다. 일부 잎은 막혀 있고 나머지는 비어 있으며, 미슬라프는 비어 있는 잎 위로만 뛸 수 있다.

한 번 뛸 때 미슬라프는 최대 k개 떨어진 잎까지 갈 수 있다. 현재 잎이 a이고 비어 있는 잎 b가 $|a - b| \le k$를 만족하면 a에서 b로 뛸 수 있다.

그림 1: 첫 번째 예제 테스트 데이터의 사이클 하나.

미슬라프는 비어 있는 모든 잎을 정확히 한 번씩 방문하고, 출발한 잎에서 끝나는 사이클을 찾고자 한다. 두 사이클은 방문하는 잎의 순서가 같으면 같은 것으로 본다. 시작 잎이 달라도 순서가 같으면 동일하다. 그림에서 2-3-6-4-2와 6-4-2-3-6은 같은 사이클이지만, 2-3-6-4-2와 2-4-6-3-2는 서로 다른 사이클이다.

서로 다른 사이클의 개수를 $10^9 + 7$로 나눈 나머지를 구하라.

첫 줄에 잎의 개수 n과 최대 점프 길이 k가 자연수로 주어진다. 둘째 줄에는 길이 n인 문자열이 주어진다. j번째 문자가 0이면 j번 잎이 비어 있고, 1이면 막혀 있다. 비어 있는 잎은 적어도 3개이다.

사이클의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.